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.
Very odd. It sounds like it's the same client computers each time? Normally I would start the troubleshooting by looking for problems on the server, then problems on the network. For example, the server might be too busy to renew the licenses at a particular time, or there may be a device on the network dropping the DHCP requests. However, if the problems reoccur with those ten computers, we'll start there.
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.