I remember seeing something similar a few years back at a company were I was then working. Laptops where running NT4 and DNS/DHCP were provided by Solaris boxes though, so your issue may be unrelated.
But here is what I can remember from it :
Only laptops were affected, and only when users were just returning from visiting a remote office, where they had connected their laptop to the local network.
I can only vaguely remember that the issue seemed to be related to 'sticky' dynamic DNS host name registration. I can't exactly tell you why now.
It would appear that on returning, the remote office's domain name appeared kinda 'stuck' inside the local configuration, so the machines would appear unable to bind to the local DHCP/DNS servers, or were simply not accepting local DHCP offers.
This may sound odd, but manually correcting the machine's domain name back to the local domain and rebooting was enough to solve the problem.
Unfortunately, because of poor communication with Unix and remote sites administrators and too little time available, we were never actually able to investigate the problem down it true cause(s).
We instead concentrated of solving the problem for the users affected.
Manually releasing/renewing the address was also enough to solve the problem, though the machines' own startup DHCP requests were not. But you had to have admin rights to do this, so I ended up renewing the address using a batch file that ran at startup via the AUTOEXNT service, specifically installed for that purpose (from the MS Resource kit).
Also, you might want to look into possible issues related to switching off vs. hibernating the laptops.
IMPORTANT NOTE : Because the AUTOEXNT service runs as system, you have to properly protect the batch file so only admins can make changes to it. Otherwise you would be creating a serious potential security issue.
Of course, desktops not travelling nearly as often were never affected. ;+D
Hope this helps.
