Network Map vs Available on the Network

All connected Vista computers always appear properly on my Network Map, but
they seem to randomly appear or not in the Network view. Those that don't
appear, are not accessible. If I manually type the computer name in an
Explorer address bar or from the Run menu, it fails (or it has shares that
are availale offline, it opens the Offline versions of the shares from that
computer).

If I restart the seeking computer, it almost always properly finds the
missing computer and talks correctly to it. But this is a major hassle and
clearly should not be needed.

This happens most often when I take a laptop off the network and use it on
other networks (Wi-Fi at airports, etc.) or let a computer hibernate or
standby. In either case, it's when that removed computer comes back to the
network that it can't see others. Note that for Hibernate, it's fully
powering down, but restoring from Hibernate often causes the problem. Again,
performing a Restart (even though that is not a full power down), generally
fixes everything.

Since the system appears propery (correct IP #, etc.) in the Network Map,
why might it not be accessible on the network?

I should note that I had similar problems in XP when laptops would leave and
return to the network. The difference for me is that in Vista, now I can see
them on the Network map, so I hope this gives an improved diagnostic to
solve this problem once and for all... or is this just an inherent problem
with Windows networking (never have this issue with Linux systems)?

Thanks,
Colin