Would you do me a favor and check the event log on the problem machine (actually on all of them ultimately) see if you see any problems regarding Browser Elections, Check windows logs->system-> then filter current log for errors, warning, information and select BROWSER from source drop down. Just to see if any of the times will coincide with the comings and goings of the machine from the network list.
We see this sometime with XP machines combined with Win7 machines, seem to argue over who's the master browser and who maintains a server list and it seems that during this time the netbios information isn't propagate properly or maybe at all.
There is a registry setting for MaintainServerList as well as for IsDomainMaster, you can probably get that info on google, but I would suggest just either resolve the issue with static IP addresses for the machines on your network coupled with an lmhosts file on all machine associating the proper netbios names with the correct ip address or else just keep using the UNC path as you've been doing. Good luck