Windows 2008 DHCP service fails - "...failed to see a directory server for authorization."

Since I've had the privilege of actually working in this specific environment, I can say with certainty that the DC that is hosting DHCP fails replication and goes unresponsive to requests for various Directory Services functions (like authorizing DHCP servers) every few weeks. This DHCP issue is a symptom of the larger replication problem.

Since the server that DHCP is on is a DC, it only ever looks to itself for authorization. When Directory Services stops functioning on it, so does DHCP.

This part really jumps out at me:

• "Not enough storage is available to complete this operation".

I'm assuming that you actually do have disk space available on the server. This points to the possibility of data or disk corruption. Have you run a chkdsk? Do the credentials the DHCP service runs under have permissions to the log directory and to the directory where the DHCP db is stored?

Ruling out those possibilities, next step is to check that there are no invalid entries in DNS for your domain, especially if there was a DC that was removed from the domain at some point. First do a nslookup on the FQDN of your domain, check to make sure there are no invalid IP addresses returned (I've seen sometimes a 2nd unused NIC on a DC with 169.254.x.x address register itself in DNS as a valid NS/DC). Next on the DNS server check SRV entries for LDAP and KRB, make sure they are all valid.