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:
 On the Clients, what is the default network port set to? Are more than one ports enabled?
 Is there a proxy setting in the Location document of the Client?
 Have you placed connection documents into the client PC with hard coded IP addresses to the server to see if the issue resolves?
 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)
 Have you tried using the following in the client to determine WHICH part of the Notes system is choking? (put in INI file)
 Simple Trace Route to the server (by name)- how long does it take between each hop?
 How about just copying a large Windows file to the server while on the same subnet and while not?
 Have you used network performance tools to see what results you get - comparing when they are on and off the same subnet?