Normally, lease expiration time should have nothing to do here, as long as clients are correctly sending DHCPRELEASE packet, at the end of DHCP client-server communication.
Also, check-ping statement in dhcpd.conf should help solve the problem or at least show the source.
According to my experience, problems with leases can come from buggy clients - process is following:
- Client starts with DHCPDISCOVER
- Server reserves IP and reply with DHCPOFFER
- Client ignore packet or never receive it and starts conversation again.
If this happen quickly, such buggy client can borrow all the leases easily. Search for such client observing conversation in logs and by
grep -i ff:ff:ff $PATH_TO_DHCPD_LEASES_FILE
On the other hand, remember that in dhcpd.leases file there are also expired leases. So it can looks like all leases are used, but it is not the case. You should easily parse this file with awk and grep (or perl), to see how many is in use.
Also - you can blank lease file and restart the server. This can help you to see how the process looks like. But be aware that if you have no manual dhcp clients (IP assigned depending on MAC), IP addresses provided for workstations could and probably will change.