Have you talked with your network folks to see about changing the DHCP lease? You may have changed the heartbeat, but the IP address may not have changed. Or the WINS database may be slow to update the records. This would indicate a network problem, so again you may want to have a chat with the network folks. You might also want to try forcing a hardware inventory on these computers reintroduced into the network.
This was first published in June 2003