So I've been fighting tooth and nail with a problem on my network with DNS. The problem is this: users couldn't access some things by domain name. Sometimes. Not all the time.
When I'd use NSLookup on their machines, everything would resolve fine. And then ping would work -- probably due to the name being added to the cached network names on the computer.
The problem only affected Windows -- my Mac machines were able to resolve all things fine.
The DNS servers on these affected machines (handed out via DHCP) were as follows:
Primary DNS: 10.0.0.5
Secondary DNS: 126.96.36.199
We added the public DNS as the secondary DNS in the event that our company's DNS servers were ever down -- the machines could still connect to the internet, even if internal queries wouldn't be answered.
And that's where the problem lies. The Windows implementation of ping uses a round-robin selection method of DNS server (random), whereas NSLookup uses the ordered lookup method (ordered - 1, then 2).
When requests were randomly using the public DNS server, they had no idea what Exchange.full.fulldomain.com was, and failed the pings.
So in the future -- make sure you have all valid internal DNS servers on your company machines - Windows' non-standard implementation of "Ping" will cause you great pain and intermittent DNS failures.