The address leases records in the DHCP Console have an icon with a pen instead of the usual computer icon even though the Host record for the DHCP Client machine is present in DNS.
The above icon indicates "Active lease, DNS dynamic update pending. This address is not available for lease by the DHCP server." DHCP is configured to "Automatically update DHCP client information in DNS" and "Update DNS only if DHCP client requests".
To correct this issue do the following:
Now the Address Lease should show the usual icon (computer icon without a pen).
DHCP console icons reference can be found at the following link: http://technet.microsoft.com/en-us/library/cc784812.aspx
PingBack from http://diggffxi.info/tags/101/200812/dhcp-server-not-leasing.html
The final fix that I found was a bit more simpler; on a Windows 2008 DNS server, just go to the reverse zone and remove all (A) records. After a couple of minutes, a few workstations started to appear on the forward and reverse zones... after a couple of hours, I had more than 50 records on both zones.