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.
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.
Best Answer
Most often when I see this kind of DHCP-not-updating DNS behavior, it is because the credentials that DHCP uses to do the updates have a problem.
To access the credentials screen - Open up DHCP, right click IPv4 protocol, select the "Advanced Tab", and then the "Credentials" button.
You should also make sure that the "Dynamically update DNS A and Ptr ..." option is checked on the DNS tab.