If your client is configured as p-node, name resolution may take several seconds until the Name does not exist message is issued.
When a WINS client get a negative query response, a second query is performed on the secondary WINS server, after waiting a default 1.5 seconds.
You can reduce this delay by using regedt32 to navigate to:
Edit or Add Value name NameSrvQueryTimeout, a type REG_DWORD entry, and set the data value less than 1500 milliseconds (0x5DC). The valid is range is 100 (0x64) - 4294967295 (0xFFFFFFFF) milliseconds.