В домене с сервером 2003 возникают запреты доступа между различными машинами
 

В офисе небольшая сеть построенная на одном домене периодически возникает ошибка при которой один компьютер видимый в обзоре домена становиться недоступным при попытке зайти на него либо с одного из компьютеров домена либо со всех сразу при этом сам может заходить на противоположный. Предыдущий админ решал проблему переустановкой системы на проблемном компьютере можно ли решить проблему менее жестоким способом. Менять имена проблематично так как в сети программы забитыми именами и соответствующими доступами и заменять их там нельзя

скорее всего адреса у вас выдаются DHCP и не регистрируются в ДНС-е.
поэтому вы попадаете по имени непонятно куда.

перестановка не нужна, надо
ipconfig /release
ipconfig /renew
ipconfig /registerdns

подробнее об этом вот тут .
Нужен способ с DNSCREDENTIAL

Gary_Evg,
Начните с просмотра журнала событий на сервере. Если есть в разделе SYSTEM ошибки, относящиеся к службе Обозреватель компьютеров (Master Browser) - решайте её.
Сочувствую.