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.
"Welcome back my friends to the show that never ends. We're so glad you could attend. Come inside! Come inside!"