I've seen this happen for a few reasons but had a new one today.
We had a new 3750 that I'd set to DHCP on VLAN1 to plug in. I then changed the native VLAN to 111 and added voice etc VLANs
Then we plugged a phone in and started seeing the Windows DHCP server fill with BAD ADDRESS entries and when you cleared them the came back in seconds.
Hmm.. unplugged the phone and PC on the back of it. Still filled the DHCP table.
Turns out the core switch had VLAN1 decommissioned but it still had a helper and so the new switch's DHCP requests on VLAN 1 were going to the server and turning up as short MAC addresses (8 or 10 characters) and Windows went no, next and so on.
Odd. I would have thought it would have said no range defined and ignored it. So the helper must be doing something bizarre.
Moral of the story: look for stray helpers on your layer 3 devices as another source of BAD ADDRESS problems.