said by Kilroy:
users will work at different locations on the network and VPN, often multiple times in a day
This is going to be a large part of it. I'm thinking that you probably have a lot of users compared to the number of addresses in the scope, with only a smaller set there at any one time.
Lease time is probably less relevant here. If anything, it is probably higher, rather than lower. How long does the computer take to restart? If possible, check to see if the DHCP option "Release DHCP Lease on Shutdown" is enabled (it probably is). I am betting it is also a Linux server.
Essentially what is happening here is that on shutdown, the client is releasing the address, but before it has a chance to re-enable the network after boot, the address is already been given out to another device.