DHCP packed with bad_addresses - not releasing

I have recently moved our dhcp server from an old NT 4 to an existing 2k3
server, we have around 60 resources that require an IP,
servers/printers/firewall have all manually assigned IPs, client PCs are all
DHCP assigned. My problem is that I cant get the dhcp server to release bad
IPs for reallocation even though the IP has expired and is not in use on the
network.

Some of the PCs still have the old dhcp server listed as their ip provider
even though this is off line, and are functioning, some pcs have lost ip but
can't get one from the server as there are no available IPs for allocation.
Thought it might be an arp cache issue but have checked every pc on the
network. Even if I assign an excluded IP the pc tells me it allready exists
on the network.

Any help would be more than welcome.
Thanks,K.