>>14
クライアントＰＣ(WindowsXP SP2)のWindows Firewallは切っても同じでした。
WindowsXP SP1のクライアントマシンでも試しましたが、同様でした。

>>15
非常に興味深い情報ありがとうございます。思い当たる点として、時と場合によってですが、コンピュータブラウズができないマシンがあったことがあります。（全て見えない訳ではなく、ブラウズできるマシンがやたらと少ないのです）
なお、ＷＩＮＳサーバーは導入しておりません。

>あとは見えない環境の中でOSレベルが
>上位のマシンがあり、それがマスタブラウザになっている）
>というのも考えられる。

プリンタ掲示板で、お尋ねするのは申し訳ないのですが、
ネットワークを検索し、>>15 さんがおっしゃっているようなＯＳレベルの一覧を作成できるようなツールはありますでしょうか？
（SSCで、NAVを導入しているマシンのOSの確認できますが、それ以外のマシンを検索はできません）
マスターブラウザが原因となって、プリンターが見えないのであれば、そのマスターブラウザを発見しなければなりません。
また、その対処方法を検討する必要があります。

引き続き、どんな情報でも構いませんので、アドバイスよろしくお願いします。