I have a Windows 2000 server running DHCP. I have a pool of about 75 IP addresses. Selective DHCP clients cannot find the DHCP server until I do an IPCONFIG release-and-renew twice. Out of the 75 computers managed, about 10 require this action upon lease expiration.
Do the systems have anything in common? If they're on the same LAN, their router could be having intermittent problems. If they're at a particular patch level, it could be a software issue resolved by installing a service pack. If they have multiple network cards, it could be a local routing problem. Unfortunately, I'll need more information to help you troubleshoot it further, because I haven't seen your exact problem before.
The Microsoft Web site section "Troubleshooting DHCP clients" may help, but your odd transient symptoms don't match any of the situations perfectly.
This was first published in December 2002