I've got a DHCP server that's configured to "Always dynamically update DNS records". Unfortunately, it's not doing its job. The client sends an Option 81 with its FQDN and all flags at 0. The ACK back from the server does not contain Option 81, and a PTR record never appears. A records are appearing properly, for what it's worth.
I believe I have resolved the problem, today, by configuring the DHCP server to use explicit credentials when performing DDNS updates. Perhaps I'm remembering incorrectly, but I don't believe this was a requirement in Server 2003.
I started by creating a non-privileged user account set with a strong password, password does not expire and user cannot change password.
To configure DHCP:
After configuring the explicit credentials, I issued an ipconfig /renew to my own workstation. The PTR record appeared immediately in DNS. This has a secondary benefit in that a failover DHCP server will have access to update records that were initially created by the primary DHCP server for the scope.