It seems that the way Windows computers resolve names of others has slightly changed in Windows Vista. For some reason, a perfectly stable and reliable Samba GNU/Linux server can be found by all computers running XP, but not by the one running Vista.
We haven't solved the problem yet, but it seems to be related to LLMNS and IPv6, based on information on a Microsoft site about LLMNS
...to be continued...