Bon alors c'est un peu le problème de NetBIOS dans un réseau à découverte automatique (sans serveur WINS). Rien ne garantit que la machine soit trouvée.
Le seul moyen pour être sûr que ça fonctionne, c'est d'appeler les machines sans passer par le voisinage réseau (démarrer ; exécuter ; \NOM_MACHINE), et si ça ne marche pas, \adresseIP fonctionne assurément.
Voir aussi si tu n'as pas un firewall qui bloque les accès dans un sens. Ah, et pour du partage qui ne soit pas "simple" (càd en dehors de Documents partagés), il faut (sauf à jouer avec gpedit.msc) que tu déclares sur la machine serveur un compte qui soit celui de ta machine cliente. Sinon, les droits ne sont pas suffisants (ou alors, il faut utiliser NET USE, en étant certain qu'il n'y ait pas eu de négociation NTLM avant, sinon ta session cliente est marquée comme étant refusée par le serveur jusqu'à ce qu'elle se termine).

C'est un peu (beaucoup) la merde, je te l'accorde ; jusqu'à Windows 2000 SP3, c'était assez simple mais depuis le SP4 et WinXP, tout a été restreint au maximum pour des raisons de sécurité.