[XPurple]

Если используете кроме tcp/ip другие протоколы, а также среди клиентов есть win9x-компьютеры, либо в качестве контроллера домена выступает NT4 сервер, то обратите внимание на wins-сервер, возможно, причина в нем. Хорошо бы привести список служб, отвечающих за NetBios/Browsing и их состояние.

про DNS: каким образом регистрируются (и регистрируются ли вообще) клиенты на сервере.
Если регистрируются, то как:
1. Автоматически (через dhcp),
2. с помощью установленной галки "Зарегистрировать.." на клиентских компьютерах.
3. Вручную.
4. Никак или методом х.з.