DHCP Bad Address Messages

We began running into some "stolen" IP addresses on one particular subnet a
few moths ago. The devices being affected are all laptops that usually
connect for only a matter of minutes to do a download/upload and then they go
back into the field. The laptops are running Windows 2000 professional. Other
PCs on the network are not having this issue.

Basically they won't get a lease from the DHCP server. Checking shows a bad
address. The log files for the DHCP server look similar to this:

11,07/05/06,18:03:13,Renew,10.250.173.52,HS-52.SAMC.COM,00E00059F0E5
13,07/05/06,18:03:19,Conflict,10.250.173.52,BAD_ADDRESS,
13,07/05/06,18:03:19,Conflict,10.250.173.52,BAD_ADDRESS,
15,07/05/06,18:03:29,NACK,10.250.173.52,HS-52.SAMC.COM,00E00059F0E5

However pinging the "stolen" address never gets a reply. I can then "fix"
the reservation by putting its MAC address back and it works fine. It is not
a single address, I have recorded over 30 addresses with this issue. The log
file on the laptop shows a stolen address, but no MAC address information is
available. The same is true on the DHCP server logs. I checked the router's
arp cache, but it only shows the MAC address of the laptop, and since I can't
get a MAC address or find the culprit online, I am at a loss.

I have verified that none of the laptops have a hard-coded address and they
are all configured to obtain an IP from the DHCP server.

We are running Windows DHCP on a Windows 2000 SP4 server. All of our IPs are
reserved with MAC addresses so our clients will always get the same IP
address. The server resides on a different subnet and a helper IP is in our
routers to allow it to hand out leases. It is the only helper address on the
networks.

We tried moving the laptops to another subnet to relieve their problems. The
problem followed them. There are about 150 workstations on this network that
are not having an issue (they are on most of the time and rarely get turned
off). There are about 60 laptops. We don't have any real IDS system to track
down a rogue DHCP server or anything. I do have a sniffer available, but
since the problem can be absent for weeks at a time or can happen multiple
times in a day, I haven't managed to get a valid capture yet.

Any suggestions on where to start or how to track down some better
information to help me troubleshoot this issue would be appreciated. Our
entire network consists of about 2500 devices on 30+ subnets, and only this
handful of laptops has run into this issue. All subnets use the same DHCP
server for getting their leases.