I'm having quite a weird issue. Had mail delivery issues to a specific domain. After looking closer, I realized that the DNS for that domain isn't resolving via the in-house Windows 2003 SP2 DNS server.

C:\>nslookup foodmix.net 
Server:  DC.DOMAIN.com
Address:  10.1.1.1

 DNS request timed out.
     timeout was 2 seconds. DNS request timed out.
     timeout was 2 seconds.
 *** Request to DC.DOMAIN.com timed-out

(DC.DOMAIN.com and 10.1.1.1 are generic values to replace the actual ones)

Even if I run this nslookup from the DC.DOMAIN.com server, I get the same result. However, all other requests are working as they should. I tried it on severs at completely separate organizations on different networks(Windows 2003 AD servers). The weird thing is some of these were having the same exact issue. However using public DNS servers work. I have tried clearing the DNS cache, restarting the server, restarting the services, etc. Nothing has worked.

One weird event I noticed in the DNS Server Event Logs that might be related is an event ID of 5504 with the following description:

The DNS server encountered an invalid domain name in a packet from 192.33.4.12. The packet will be rejected. The event data contains the DNS packet.

For more information, see Help and Support Center at http://go.microsoft.com/fwlink/events.asp.

In the data section below, I can see the following mentioned:

ns2.webhostingstar.com

Which happens to be the nameserver for the domain in question. Several discussion threads and a MS KB have pointed to disabling EDNS. I have done this via "dnscmd /config /enableednsprobes 0" and it has not fixed the issue.