Make sure the hosts and lmhosts.sam are unmodified.
In the IPv4 Properties of the adapter click advanced and then the WINS tab. Make sure that Default or Enable NetBIOS is enabled over TCP/IP. Well, presuming you want to use WINS.
nbtstat -n - should show the names resolved in the cache
ipconfig /flushdns to purge the DNS cache, albeit that's a longshot as an issue (it only has a TTL of an hour)
ipconfig /displaydns can show the entries in the DNS cachehttp://support.microsoft.com/kb/922120
You'll need to request the Hotfix (it's painless). Won't promise it will fix the problems, but it will add LLTD to XP SP3, which is a better solution than WINS.
All of my written content here on TR does not represent or reflect the views of my employer or any reasonable human being. All content and actions are my own.