[0] Are you 100% sure that if the server and the client are in the same subnet, it works fine, but otherwise no?
If so, here are some ideas:
[1] On the Clients, what is the default network port set to? Are more than one ports enabled?
[2] Is there a proxy setting in the Location document of the Client?
[3] Have you placed connection documents into the client PC with hard coded IP addresses to the server to see if the issue resolves?
[4] Are the server names in the Location document the NOTES Server names or are they hostname style? (i.e. Server1/Test vs server1.testworld.com)
[5] Have you tried using the following in the client to determine WHICH part of the Notes system is choking? (put in INI file)
Client_Clock=1
Debug_Outfile=SOME-FILENAME-TO-STORE-OUTPUT
[6] Simple Trace Route to the server (by name)- how long does it take between each hop?
[7] How about just copying a large Windows file to the server while on the same subnet and while not?
[8] Have you used network performance tools to see what results you get - comparing when they are on and off the same subnet?
Example:
http://dast.nlanr.net/Projects/Iperf/