net work connections refused on first attempt on windows server

I am encountering a very unusual error at my work place. When connecting to
servers outside of the local network from Windows Server 200x by the DNS host
or FQDN name the first connection is rejected however the second attempt
always succeeds.

example:
net use \\remoteserver.company.com\admin$ /user:<domain>\<user> <password>

The following error is diplayed every time:
System error 64 has occurred.
The specified network name is no longer available.

However if i immediately reissue the same command it always succeeds

This issue appears to only be happening on Windows Server 200x however it
does not occur on XP.

I've determined its not cable, switch or other hardware as i plugged my
laptop into the same switch port with the same cable and it works fine and it
is occuring on at least 5 different servers on different switches.

Any help would be greatly appreciated this is causing us some major grief.

One additional piece of information, if i connect to the servers by IP it
always succeeds.