There is some kind of handshaking going on between the workstation and the DNS server

Actually from your description, I think this is happening from some kind of Windows protocol voodoo. Like at the WINS or NETBeui level. Try pinging said fresh Windows installation from a non-Windows machine...