When a client restarts, it tries to renew/discover it's previously owned address. If it does not receive a response, it waits 5 minutes before attempting to discover a new address.
To resolve the problem, first upgrade to Service Pack 6 (SP6).
Use Regedt32 to navigate to:
On the Edit menu, Add Value name DhcpUseLargeNumberOfRequests, a type REG_DWORD. Set the data value to 1.
Prior to upgrading and setting the registry entry, the client can try to workaround this issue by typing: