The DNS update requests are issued by the client, and the DHCP server perform those updates on their behalf. When a client is renamed, it should request both, the creation of the new DNS records, and the deletion of the old DNS records.
The server can be configured to perform DNS updates regardless of whether the client requests this action or not. You could try this, to see if it helps.
To modify this setting, select the Enable DNS dynamic updates according to the settings below check box and click Always dynamically update DNS A and PTR records, which is located in Properties on the DNS tab on the applicable DHCP server or on one of its scopes.
Another possibility, if you have more than one DHCP server, is that one DHCP server creates the DNS records (and thus becomes the owner of the name), but later when a DNS update is requested for that client, if for any reason the owner DHCP server is not available, no other DHCP server can update the records, because they are not the owners of the name.
If that is the case, the problem could be solved by adding all DHCP servers as members of the DnsUpdateProxy built-in security group, but this involves other security-related issues.
