I've since found that one of our routers is detecting the messages being sent from one client to another contain different target IP addresses of that to the Server, and then our router decides that these messages should then be sent via a different external port. This is where the problem was coming from. Using a bit of port prediction, this hurdle can be overcome most of the time.
For those who are interested, most of the time if a connection cannot be found at the presumed port, it will most likely be at the very next port (ie. Port# + 1). If not, it gets a little bit complex from there to work out.