Alright AC, looks like you have discovered why MS peer networks sucks donkeys.
I'll try to help though.
I'm going to make some assumptions and then explain MS networking.
1) You can ping by ip address, this means layers 1,2,3 are good.
2) All machines are on the same broadcast domain (no router or filtering between them, on SAME IP SUBNET)
3) None of the other computers have any other network adapters (even dial-up)
4) You don't have any WINS servers running
5) All machines have the same WORKGROUP name
6) All computer names (netbios names) are no longer than 14 characters and do not contain special charaters other the alphanumberic, -, _ and space (for god's sake don't put spaces in a computer name people)
With those assumptions in place your MS network will be operating in a broadcast mode and should be fine. PCs will locate Netbios over TCP (NBT) names with a subnet broadcast/layer 2 broadcast. Windows DOES cache netbios names, check to see if your name resolution is working by going to command prompt and typing "net view \\NETBIOSNAME" where NETBIOSNAME is the computer name. If you get a list of shares on the computer then great! name resolution/browsing is working. If not then we have to look at other things. On DOS prompt type "nbtstat -c" and see if you have any netbiosname/ip address pairings.
Name Type Host Address Life [sec
----------------------------------------------------------
BF_BDC_1 <20> UNIQUE 172.21.1.189 660
BF_PDC_1 <20> UNIQUE 172.21.1.190 660
If not then somehow you cannot resolve NBT names and will never work.
If you can ping that means your hosts routing table/arp tables are fine.
You can edit a file called LMHOSTS in the windows directory to manually map the NBTnames to IP addresses.
Maybe the subnet master browser is screwed up (the dipsh!t down the hall likes to play with registry settings does he? or maybe a soft firewall on his machine?). This computer is arbitrailiy decided (simple explanation)
Other than checking nbtstat -c to see if names are resolving and pings work I can't be much more help without a packet trace. If you are able to get a capure then e-mail to me and I can help.
cheers!
ps - MS networking by default (maybe design?) does exactly what you described from time to time. The browse list will just up and get screwed. Best to use a WINS server, still a browse list but at least comes from a reliable source.