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:

HKEY_LOCAL_Machine\System\CurrentControlSet\Services\Dhcp\Parameters

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:

ipconfig /release
ipconfig /renew