How to setup redundant dns and dhcp servers with automatic dns updates on Ubuntu

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?

The master/slave configuration (also known as “zone transfers,” AXFR or IXFR) is the standard configuration used by most DNS servers. For that reason alone, it’s what I’d recommend, even though it’s complicated.

Although I recommend it for interoperability, and because it’s easy for other admins to understand, that doesn’t mean it’s technically the best way to do it.

Daniel Bernstein (of djbdns/tinydns) strongly prefers rsync and has this table comparing rsync vs. zone transfers. rsync works great with tinydns but I’ve never tried it with bind.

If you try it, keep in mind that you’ll probably be writing a script that gets run by cron. Another admin who looks at your DNS configuration won’t necessarily know this, or know where to find the sync script. By contrast, the regular zone transfer config is right there in your zone files, making it explicit. Whether this matters depends on how many other admins you deal with and how informed you expect them to be about your DNS configuration.