When you go to a command prompt and type "nslookup" the response will be something like this:
Default Server: dnsserver.domain.TLD
If the DNS server that you expect is not shown in the "Default Server:" then that PC's DNS settings are suspect. It could be that the DHCP options aren't set correctly or if you use static IP information on that PC, those aren't entered correctly. Otherwise, there is a basic TCP/IP connectivity problem...
Question 1: Can you ping the DNS server?
The DNS server itself will be set to point to itself for DNS and the DNS service will by default look to root hints for resolution. You may want set up forwarders as Cédric Boivin has suggested. However, I'd suggest OpenDNS for speed, security and reliability reasons. Check out this tutorial to set up forwarders.
Question 2: Does nslookup behave this way on all computers in the domain?
Question 3: Does nslookup behave this way on the DNS server itself?
At the end of the day, I'd suggest using Network Monitor on the affected PCs and using a capture filter for DNS traffic to see what is and is not being transmitted and what, if any, error codes are being returned.
Question 4: Are you sure that the hardware firewall doesn't have a rule that manipulates DNS traffic at all? It could be set to block DNS traffic under certain circumstances.