Netzwerkumbgebung bleibt leer

Habe ein Problem in unserem kleinen WinXP Netzwerk. Und zwar bleibt bei manchem Windows XP SP2 Rechnern
Die Netzwerkumgebung leer. Manchmal tauchen die Rechner wieder auf aber spätestens nach dem Neustart sind sie weg.
Alle Rechner lassen sich aber stets anpingen und auch über Suche oder Direkteingabe im Adressfeld erreichen. Wenn man die automatische Suche nach freigegeben Ordnern aktiviert so findet er auch immer sofort alle Ordner und listet sie auf.
Die Arbeitsgruppe ist auch stets sichtbar nur die Rechner da drin nicht....
Das Problem ist auf einmal aufgetaucht und ist auf den ersten Blick nicht logisch erklärbar. Das einzige was sich in lezter Zeit verändert hat ist die Installation von SP auf dem Win2003 Server der aber nur als Sicherungsserver und VPN Server fungiert.
Was kann das Problem sein?