I've had the same problem, and am almost positive I found a working
fix (it works on my systems). I had previously tried all the other
mentioned solutions, including disabling Dynamic DNS, turning on or
off the option for the network adapters to request registration in
DNS, adding reverse lookup zones, etc, but to no avail.
My solution is probably only applicable to domain controllers running
the DNS server service. These errors seem to be generated by programs
trying to resolve domain names to connect back to the server to
authenticate, but can't find it if the DNS server service hasn't
started yet, failing the request. The solution seems to be adding DNS
as a dependency to these services. On a clean Windows 2003
installation, promoted to a DC, with IIS installed, I needed to make
W32Time (Windows Time Service), NtFrs (File Replication Service), and
SMTPSVC (Simple Mail Transfer Protocol (SMTP)) dependent upon DNS (DNS
Server). See
http://support.microsoft.com/default.aspx?scid=kb;en-us;193888&Product=win2000
for details on how to do this.