２年ぐらい前、私もこれで相当はまりました。

NetBIOSってなかなかドキュメントがないんですよねぇ。

で、仰せのとおりでして、
samba関係を漁っていくとだんだん紐解けるんですな。

まぁ、私の場合、仕事とはいえ
自分の社内で動かすだけなので、動けばいいや、
っていう感じで解決したのですが、それでも結構曲者でした。

私が覚えている要点(sambaがファイルサーバーの場合)は…
・つべこべ言わずにポートの137〜139を開けろ
　(TCPとUDPの区別は忘れた。調べてください)
・ブラウジングとデータ転送のポートは別だということを忘れるな
・XPを使うときはポート445も開けろ？
　(私の場合sambaサーバーへのアクセスに445は使ってないと思ったけど)
・XPHomeは普通のNetBIOSは使えない(ドライバがないだけらしいが)
　だからNetBIOS over TCP/IPを生かせ、ということらしい
　(当たり前だけど純正NetBIOSだけの通信ならIPアドレスは要らない)
・コンピューターとユーザー名に日本語は使うな
　(使えるけどいろいろと面倒)
・他のWindowsマシンがマスタブラウザにならないようにレジストリを書き換えろ
　(マスタブラウザになっているパソコンをシャットダウンすると一時的にブラウジングできなくなったり、居るはずのないマシンが表示されたりする)
・sambaサーバをマスタブラウザになるようにしろ

これで私の職場は大体うまく回っています。
(とはいえ、高々クライアント１５台ぐらいの小さな職場ですが)
ただ、どうしても１台だけうまくブラウジングできないクライアントがいたので、
lmhostsを書き換えて強制的にsambaサーバーを見せています。