How is this the DHCP server's fault? DHCP is designed to reassign unused leases to new clients if the subnet is all leased out.
The DHCP will ping an address before leasing it, and if it gets a response then it will not lease that address.
Keep in mind if aa client wants an IP, it is supposed to do DHCP discovery every time it connects to the network, even if it's lease isn't up. See http://en.wikipedia.org/wiki/Dynamic_Host_Configuration_Prot...