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:

HKEY_LOCAL_MACHINE\System\CurrentControlSet\Services\NetBT\Parameters

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.