Unresolved DNS name

I would run a packet dump on a few of these boxes until it happens. See if you can find anything network related. Maybe you will see some packets that give you an idea if it is not that.

Can a group policy in Windows set the DNS server. Maybe somehow there has been a strange GP applied on the domain?

Update:
I have never done this, but since it seems like you are getting a little desperate, what about blowing away the current DHCP database. These instructions say how to back up the mdb file, so maybe moving it somehwere else will make it so DHCP creates a new one after restarting. That might fix the problem...

The thing that doesn't jive in my mind, :-), is why clients would be getting new information if their lease hasn't expired yet and they haven't rebooted... is this what is happening?

Windows queries DNS in this order:

• hosts file
• local DNS cache
• Preferred DNS servers
• Other DNS servers

MS also has an article describing how the DNS server list is obtained:

The DNS Client service uses a server search list, ordered by preference. This list includes all preferred and alternate DNS servers configured for each of the active network connections on the system.

The list is arranged based on the following criteria:

• Preferred DNS servers are given first priority.
• If no preferred DNS servers are available, then alternate DNS servers are used.
• Unresponsive servers are removed temporarily from these lists.

Windows has an escalating timeout for DNS requests:

Value      Default value  Attempt
1st limit       1 second  Query the preferred DNS server on a preferred connection.
2nd limit      2 seconds  Query the preferred DNS server on all connections.
3rd limit      2 seconds  Query all DNS servers on all connections (1st attempt).
4th limit      4 seconds  Query all DNS servers on all connections (2nd attempt).
5th limit      8 seconds  Query all DNS servers on all connections (3rd attempt).
6th value                 (Must be 0.)

I could not find a clear answer on this exact point, but it sounds like if it doesn't get a response from your primary DNS in 1 or 2 seconds (1st or 2nd attempt, respectively), then that server will be removed from the DNS server lookup list for 15 minutes, and so it will use the secondary DNS servers. Since those servers have up to an 8 second timeout, they are much more likely to respond. (It's unclear to me if it continues to query the preferred DNS server during the 3rd+ attempt if it's already failed).

I also suspect that you do indeed have a WAN latency issue for this geographical area, as it would explain why the timeouts are working.

One solution is to change the DNS query timeouts, using the DNSQueryTimeouts registry parameter. See also http://drewthaler.blogspot.com/2005/09/changing-dns-query-timeout-in-windows.html

Another solution is to put a local caching DNS server on the network, and have the clients use that. You can use a DNS server that may be built in to a router, or install something like dnsmasq.