Sounds like name resolution issues. When the servers on different segments you could create an LMHOSTS file to point to the other servers IP address.
If you are unfamiliar with LMHOSTS files:
they go into the \winnt\system32\drivers\etc folder. There is NO extension on the filename. Create the file then with a text editor type in the IP address servername #PRE
example:
10.10.10.10 exchange1 #PRE
The #pre puts the servername and address in the netbios name cache, so it can quickly find the address of the server. After creating the file from nbtstat -R, to load the LMHOSTS file into the cache.
Hope that helps.