What happens if a machine gets a SYN/ACK packet without sending initial SYN packet

We had this exact same problem. Just disabling TCP timestamps solved the problem.

sysctl -w net.ipv4.tcp_timestamps=0

To make this change permanent, make an entry in /etc/sysctl.conf.

Be very careful about disabling the TCP Window Scale option. This option is important for providing maximum performance over the internet. Someone with a 10 megabit/sec connection will have a suboptimal transfer if the round trip time (basically same as ping) is more than 55 ms.

We really noticed this problem when there were multiple devices behind the same NAT. I suspect that the server might have been confused seeing timestamps from Android devices and OSX machines at the same time since they put completely different values in the timestamp fields.

For closure: the problem was a stupid bug in my code (in the client).

The client in this case uses nonblocking sockets, so the connect() call will return immediately while the kernel keeps waiting for the SYN,ACK packet from server. Unfortunately the client code was very impatient: if the connection wasn't established after a few hundred milliseconds, the client would call close() on the socket.

In some rare cases the SYN,ACK packets from the server would be delayed by several hundred milliseconds on their way through the network. When the delayed reply finally arrived at the client host, the kernel would see the socket was already closed, and would treat the SYN,ACK reply as belonging to an invalid socket. That's why it would reply with a RST packet to the server.

So yes, it is possible for the application code (using normal BSD-style socket API under Linux) to cause this RST packet: by using a nonblocking socket and closing the connection while the three-way handshake is still in progress.