Name Resolution
In a native W2K network DNS is the ONLY method of name resolution; NetBIOS is there strictly for backwards compatibility with NT4 and 9x.
In a mixed network, you're likely to be using WINS and DNS together.
So check out the WINS server - occasionally WINS records can get messed up, and need tombstoning off the server, especially if a hostname has changed IP and somehow neglected to tell the WINS server about it.
The other thing to check on a W2K DNS server is that it is configured to allow dynamic updates. If you're paranoid, turn on secure updates - that will only allow authenticated workstations to update the DNS server.
--
Peter
Shill For Hire