We were having some weird DNS issues recently with our DNS servers at work. We recently upgrade one of our internal domain controllers with Active Directory-integrated DNS services to Windows Server 2008 R2. After the upgrade we found that DNS queries for some hosts did not resolve while others worked just fine. Another domain controller running non-R2 Windows Server 2008 would resolve the queries just fine.
One of our network engineers stumbled across a Microsoft KB article describing our exact problem:
http://support.microsoft.com/kb/832223
The long and the short of it is Windows Server 2008 R2 DNS servers can use EDNS0 queries which will increase the size of the DNS UDP packet. Many firewalls will block UDP packets larger than 512 bytes. By disabling EDNS probes on the DNS server the packet size is lowered and thereby will almost always be smaller than 512 bytes which will get you passed most firewalls.
To disable EDNS probes on Windows Server 2008 R2 DNS servers, just open a command prompt and issue the following command:
dnscmd /config /enableednsprobes 0
NOTE: there are supposed to be 2 'e's in that command enableednsprobes
Now you can stop pulling out your hair when only some of your DNS queries fail.
Enjoy,
Flux.