Je server a ty XP v jednom subnetu ? Máš někde rozjetý WINS server ? Co ti vrací nbtstat -c ? Nemá ta stanice s XP více síťových rozhraní ?

EDIT:
Ještě nastartuj gpedit.msc a v local security zkontroluj jestli je Domain Memberigitally encrypt or sign secure channel data (always) Disabled (tipl bych, že v tomto bude zakopaný pes).
A taky zkontroluj eventlog na errory.