DHCP Leases

I am doing some testing on Windows 2000 using dhcp. I have a dhcp server setup with 3 available addresses. Once all the leases are assigned, I disconnect one of the clients until its lease expires. I then take a new client and connect it to getthe free address. What happens is this new client cannot get the released address for 40 to 50 minutes.
Any suggestions on why it takes so long for the released address to actually be available would be appreciated.