I've been running my RedHat 7.2 server for several years now using DNAT and SNAT in iptables to manage my network. Quite recently I noticed that one of the computers can't use the internet, the SNAT translation works but when the remote computer sends packets back, the DNAT rule doesn't seem to work, as the packet doesn't travel any further after arriving at the router.

Apparently a reboot of the router fixed the problem, but today (after no changes on the router whatsoever) another computer got the same problem. The exact same problem, and it is for that IP, as changing to another IP makes the computer work like normal again. The same problem occurs in Windows and Linux, so the problem must be at the router.

A reboot of the router isn't entirely out of question but I'd like to solve this problem as different hosts randomly failing isn't acceptable. I've tried to flush and reload the iptables but it didn't help. Any ideas?

Here's a tcpdump dump of the problem:

13:39:39.351312 local-1.35033 > remote.http: S 3143142374:3143142374(0) win 5840 <mss 1460,sackOK,timestamp 5701693 0,nop,wscale 0> (DF)
13:39:39.351532 local-1-pub.35033 > remote.http: S 3143142374:3143142374(0) win 5840 <mss 1460,sackOK,timestamp 5701693 0,nop,wscale 0> (DF)
13:39:39.363325 remote.http > local-1-pub.35033: S 1835049943:1835049943(0) ack 3143142375 win 49232 <nop,nop,timestamp 138598212 5701693,mss 1460,nop,wscale 0,nop,nop,sackOK> (DF)

local-1 is the host with problems, in the local network.
local-1-pub is the public internet ip for local-1, the ip that SNAT/DNAT uses.
remote is the remote host.

So SNAT works, but when remote sends traffic back to local-1-pub, it doesn't DNAT it to local-1 as it should. On local-1 /proc/net/ip_conntrack says that the request is unreplied.

Is the Linux server acting as a router, or co you have the firewall before your router?

The linux server is the router/firewall.
The setup looks like this:

host <-> router <-> remote

where router has host's public ip assigned to it, which is then DNAT/SNATed. The tcpdump is taken at the router.

Personally I belive this is a bug of some sort, but I can't upgrade my kernel/system quite yet.

Well, I tried the same thing I've tried many times before, deleting the iptables SNAT rule and adding it again, and now it works! But it's still a mystery.