Window scaling was definitely on my radar, but IIRC the Linux SYN cookie implementation is supposed to encode if this TCP option is set in the initial SYN as well, so I don't see how this would explain thing unless the implementation is broken. I'm not sure if I understand what you're saying about SYN+ACKs not being retransmitted, I think they should be if they get lost, it's only the final ACK from the client that doesn't get retransmitted if its lost, but that would cause different symptoms.
Yeah, it's supposed to be encoded, but it's possible it's broken. Given that you can reproduce it with a low somaxconn, it seems like the router wasn't the problem, the router just was able to more easily trigger the problem.
> I'm not sure if I understand what you're saying about SYN+ACKs not being retransmitted, I think they should be if they get lost, it's only the final ACK from the client that doesn't get retransmitted if its lost, but that would cause different symptoms.
SYN+ACK will normally be retransmitted, but if you're in synflood conditions, it means the kernel is going to throw away state for SYN+ACKs, and then it no longer has the state to retransmit. It will reconstruct the state if it gets an ACK that is a decodable syncookie, or if it gets a retransmitted SYN, since it'll make a new SYN+ACK for that (although that may end up with a different sequence number).
Did you confirm the packets were the same on both sides of the router? This pattern sounds like possibly network microbursts, which can lead to dropped packets -- maybe the replacement router had a larger buffer so you didn't drop any packets, and things worked better.
I've also seen some exciting bugs with SYN cookies on other platforms, it's possible there's some encoding error leading you to a very small window -- something wrong with the window scaling negotiation perhaps? If you've got enough incoming syns that syn+ack state is being dropped (so syncookies are being used to finish the connection), you're also going to not retransmit syn+acks, so then you need to wait for the SYN to be retransmitted.