Am I right in assuming this is DHCP on a Microsoft server, rather than something different?
If so, can you please post a screenshot of the entries you're seeing?
There can be a number of reasons why this might occur. The following is an example.
http://social.technet.microsoft.com/Forums/windowsserver/en-US/0ef9b4b1-f14d-4e55-8760-150ddd22420b/dhcp-server-bad-address-issue?forum=winserverNIS
Can you also confirm if there is a DHCP relay/helper in the client VLANs? I would imagine there is? What is it? I've seen some IP routing devices corrupt DHCP relayed messages before.
Depending on what the above reveals, the next best step might be to run a sniffer on the server to watch the DHCP requests coming in and replies out. That will almost certainly identify root cause.