I have a Windows XP Pro notebook PC that was working fine, then all of a
sudden it couldn't log in to our domain.  I tried unjoining it from the
domain and then re-joining it, but that now fails with the following error:
____________________
The domain name XXXXX might be a NetBIOS domain name.  If this is the
 case, verify that the domain name is properly registered with WINS.

 If you are certain that the name is not a NetBIOS domain name, then
 the following information can help you troubleshoot your DNS
 configuration.

 The following error occurred when DNS was queried for the service
 location (SRV) resource record used to locate a domain controller for
 domain devil:

 The error was: "DNS name does not exist."
____________________

I double checked our WINS servers.  They are set up properly.  When the
notebook is powered up, it does get DHCP from the server, which is the same
server that runs as the primary WINS server.  I can ping any IP I need to
from the problem notebook, I just can't get it to join the domain.  I have
used Server Manager to remove it from the domain.  I have also tombstoned
and then deleted the PC's WINS entries on the server.  No good.  I have
Googled the heck out of this problem and have found numerous instances of
it, but none of the suggestions seem to resolve the issue, including setting
up the LMHOSTS file to manually name the PDC.  I've also set the NetBIOS
setting to default, which means it should pick up NetBIOS properties from
the DHCP server's config.  Just to be sure, I even switched the NetBIOS
setting to "enable NetBIOS over tcp/ip"  Still no good.

It may be coincidence, but I'll mention this anyway.  It seems that this
happened at around the same time we brought a Windows Server 2003 server
online in stand-alone mode.  The server doesn't participate as a domain
controller, so I didn't think it would have any effect on PCs throughout the
company, but I have noticed that our XP workstations seem to pick up group
policies from the 2003 server even though they're not authenticating against
it (or at least they're not supposed to.)

There was also a Local Security Policy entry that I changed as suggested by
one of the articles I read.  It was "Local Policies / Security Options /
Domain Menber: Digitally encrypt or sign secure channel data"  That change
also did not help.

So, as it stands right now, I can bring the PC up in workgroup mode and can
get DHCP from the domain's DHCP server.  I can also ping IPs on the local
network.  I just can't get it to join the domain.  Also, I just discovered
that this seems to be the case with ALL new XP PCs.  I just tried to set up
another brand new XP Pro box and am getting the same error.  Anyone have any
ideas?

Many thanks,
Mark.