If you manually delete the record, then run FlushDNS and RegisterDNS command, will the record be updated successfully?
I'm not sure - what I determined is that if I use registerdns command the host does actually register. The issue is that I was looking at the wrong DNS server. It seems that when clients register with DNS, they lookup the SOA record for the zone and then choose a server (seemingly at random) to register with. If scavenging is not enabled on the zone, the record timestamps do not replicate between DNS servers so I was looking at a server that showed an old timestamp, but when I looked specifically at the server the client registered with I did see an updated timestamp.
Did you mean that you are not using windows DHCP server? For this non-windows DHCP server, did you configure it to perform dynamic DNS updates on behalf of the DHCP clients?
No, there is no integration between DHCP/DNS for DDNS registration. I am relying on the clients themselves to register with DNS.
In addition, please check the ownership of these problematic DNS record and compare with normal DNS records' ownership.
All of the records show that the computer that created it has permission to update it. Is there anything beyond that that I would need to check?