Well, the reason I mentioned DNS is that this will happen if the PC thinks it
can't get to a Domain controller. If a PC goes on thinking it can't get to a
DC for too long, it drops out of the domain. If something is not fully
functional about DNS, you'll get slow login athentications, trouble browsing
the domain, and the workstations will not be able to do their computer
account registrations with the domain controllers.
From one of the PC's that has dropped off already, you might do a ping to
all of your domain controllers by name. If you get a "host not found" for
one or more of them, then something's not right either with the settings on
the pc itself (as mentioned before), or with the DNS server(s).
I've found these commands handy for troubleshooting dns:
ipconfig /all
ipconfig /flushdns
ipconfig /registerdns
Flush will clear out the pc's local cache
registerdns would need to be run on a computer that was not registering to
DNS correctly (i.e. if you find that none of the workstations can ping
DCONTROLLER1 by name, then on DCONTROLLER1 run the registerdns command)