I was experiencing very weird DNS issues with a Windows Server 2008 R2 machine.
While resolving external domain names, it would sometimes come back with a response and some times with a timeout.

I tested this using nslookup and using the server parameter to point to the Google public DNS server. I am trying to resolve http://www.microsoft.com

nslookup
server 8.8.8.8
http://www.microsoft.com

> http://www.microsoft.com
Server: google-public-dns-a.google.com
Address: 8.8.8.8

DNS request timed out.
timeout was 2 seconds.
*** Request to google-public-dns-a.google.com timed-out
> http://www.microsoft.com
Server: google-public-dns-a.google.com
Address: 8.8.8.8

DNS request timed out.
timeout was 2 seconds.
DNS request timed out.
timeout was 2 seconds.
*** Request to google-public-dns-a.google.com timed-out
> http://www.microsoft.com
Server: google-public-dns-a.google.com
Address: 8.8.8.8

DNS request timed out.
timeout was 2 seconds.
Non-authoritative answer:
Name: lb1.www.ms.akadns.net
Address: 65.55.57.27
Aliases: http://www.microsoft.com
toggle.www.ms.akadns.net
g.www.ms.akadns.net

As you can see, 1 out of 4 requests succeeded. Something was corrupting my DNS query.

In this scenario, Microsoft ForeFront Threat Management Gateway 2010 (TMG 2010) was used.
The client, in this case a DNS server, was placed in the internal network and was NAT’d thru the external interface of the TMG, which was an interface with public IP addresses.

Somehow, the query was not arriving at the external DNS server.
Testing the same queries directly from the TMG, no issues were active.

It had to do with the internal-external NAT translation and specific for DNS traffic, because HTTP/S traffic was working without any trouble.

After some investigation NIS (Network Inspection System, part of the Intrustion Prevention System) was doing something with the queries. In our case NIS was dropping these queries.
We added our DNS server to the NIS exclusion list and the resolution issue was gone!

Since we are yet preparing to implement an alternative to TMG we didn’t see the urge to research this issue further.

Hopefully this will help some people resolve DNS issues with their clients behind TMG.

We will add NIS exclusions to all of our internal DNS servers to prevent DNS issues to arrise in the future.