TCP reset after SYN ACK possibly related to "no route to host"

I have a problem with one of our clients trying to initiate a TCP connection to our server but it fails. In tcpdumpI see, that the client's device sends a SYN packet to which our server correctly replies with a SYN ACK. Immediately after that, our server receives a RST packet. After a few seconds the procedure repeats. Strangely enough, the connection is correctly established from time to time (about every 2 days around 8:30 am). I have tried redirecting the packets to another server but get the same problem with that server. Today I tried connecting the other way round. Our client currently does not have a port opened in his firewall, but I tried connecting anyways to see what happens. I used ssh to try the connection from different machines, here is what I discovered: From my personal computer (Mac OS X 10.10): ssh: connect to host x.x.x.x port 22: Connection refused From the server that is receiving the SYNpackets (Debian 8): ssh: connect to host x.x.x.x port 22: No route to host From another server in a different hosting center (Debian 7): ssh: connect to host x.x.x.x port 22: No route to host From another server in a larger company (Debian 7): ssh: connect to host x.x.x.x port 22: Operation timed out The response I get from my personal computer at home is what I expect if the port is not opened in the firewall, but I am confused by the different outputs I get from the different servers. Pinging the client's IP from any of these machines works fine. Could I be looking at a routing problem here, where my SYN-ACK packages are routed incorrectly and therefor (almost) never reach the client? Do you have any suggestions on how to tackle the problem? Should I contact the client's ISP, or maybe my server provider? Thank you for your help. **UPDATE 1:** I did some further research on Jeff's Questions. Here are my results:

IP TTL SYN: 55
IP TTL RST: 59

I am currently waiting on the client to grant me access to his network, so I cannot currently see if he receives the SYN-ACK or if he sends the RST Traceroute:

1  x.x.x.x  25.793 ms  5.516 ms  5.516 ms
 2  x.x.x.x  4.140 ms  4.172 ms  4.166 ms
 3  x.x.x.x  4.158 ms  4.147 ms  4.139 ms
 4  x.x.x.x  9.855 ms  9.877 ms  9.874 ms
 5  x.x.x.x  15.506 ms !X  15.753 ms !X  15.970 ms !X

The traceroute from my computer at home ist the same on the last two hops. Both traceroutes have 5 hops. There is no firewall or load balancer at the server end. The routing tables look good on the servers receiving the no route to host. They mainly consist of the default route and the local subnet route both working without a problem on all other occasions.