Thanks for the replies so far.

Compared setups etc, and everything checks out. Apart from one really interesting anomaly.

Company (A) which has no problems. When I try a tracert to the server IP it times out continuously. It pings the server IP however

Company (B) Which has the problems runs a succesful tracert and ping to the IP, yet they cannot connect.

What I cannot get my head around is that when someone connects via a 3G modem it logs him in fine, and then without closing the app, disconnects the 3G and connects back onto the network and then continues to use the app successfully. So it seems the only problem is during authentication. Does the logon procedure run on a different port than the default 1433? Or does something special happen during authentication?