Linux – Client DHCP on Linux seems to not be updating Windows AD DNS

So basically you want your client to send their hostname to your DNS server ?

This works great with Windows clients, but for Linux machines, I would go the other way around : set your clients to ask the DHCP server for an IP and a hostname. Using the "request host-name" option, dhclient asks the DHCP server to send a hostname along with the IP address, then sets the hostname of the VM.

Of course you'll need to prepare, in your DNS, a hostname for each IP address in the DHCP range.

This way you don't have the DNS cache / propagation delay problem, and you may have a central place with all the IP and hostnames - your DNS server.

I don't know wether your appliance's DHCP server supports sending hostnames - most does, but I think that's the easiest way for Linux clients.

Note: If you configured your DHCP server so that the same machine always get the same IP address (e.g. using mac address) then it will, obviously, always get the same hostname too. On some DHCP server, you can use directly hostname instead of IP address in the config files.

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?