Here's an article from Microsoft that describes the dynamic DNS process with their DHCP server: http://technet.microsoft.com/en-us/library/cc787034(WS.10).aspx
The stock behaviour of W2K and up is for the client to request the DHCP server register the PTR record on behalf of the client, and the client registers the A record itself. The DHCP server can be made to register the A record and the PTR record (including for pre-Windows 2000 clients that can't make DDNS registrations themselves).
There is an optional setting to have the DHCP server delete the A and PTR records when a lease is discarded. If the lease hasn't time-out, though, the records won't be deleted.
You absolutely should be aging and scavenging your DDNS zones. If you're aging and scavenging, this will eventually "purge". If you're not, it won't.
This Microsoft support article explains how to set the TTL value for DNS resource records registered by DHCP servers (originally in a hotfix, now just built-in to the OS): http://support.microsoft.com/kb/322989
To alter the behaviour of client computers in DNS registrations, have a look in Group Policy in the DNS Client node under the Network subnode of the Administrative Templates node of the Computer Configuration. In there, you'll find that you can force the clients to register their PTR records, rather than having it done by the DHCP server (if you so desire), and you can set the TTL on records registered by clients.
I'm not sure why this would suddenly start occurring. Some configuration had to change, but I'm at a loss as to tell you where. Start talking to your co-admins about any changes they might've made in the DHCP server configuration or in the group policy settings for clients' dynamic DNS behaviour.
I can't say I've seen the behaviour of multiple clients registering the same PTR record. That's odd. I'll have to defer to someone else on that. I will say that all of my reverse-zones are always AD integrated and require secure updates, but I don't know that that would have an effect on this.
In my experience, just having aging and scavenging turned on makes a world of difference in eliminating stale records. The default 7 day interval has worked well for me.
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?
Best Answer
For a quick fix, try running this on the client computer:
This should update the DNS record for this client.
Also, you might want to take a look at this document which explains how to configure Dynamic DNS Updates on Windows Server 2003 (We don't have Server 2008 R2, so I can't tell if it applies to you - but I don't think it will be all too different).
http://support.microsoft.com/kb/816592