Sounds like a NetBIOS issue. Not much you can do about that.
I tried running one of my Samba machines as a WINS server, and telling all the others to use it: it doesn't help, much. What I admire is the sheer, apparently non-deterministic, unpredictability of Netbios from one day to the next.
Edit: today, all 6 of my netbios machines and an AFP shared host alias are showing up at once in Finder, without looking for them. This is unusual.