Should I do the stateful matching with iptables for nat table?

Solution 1:

No, you don't need that.

Dynamic NAT rules always use conntrack tables. So this is useless (and wrong). The nat table is traversed only by first packet of the connection, so it'll only see --ctstate NEW packets. It never sees --ctstate ESTABLISHED packets, because these don't traverse rules. If the packet is found in the connection tracker nat table, it has the recorded translation applied and proceed with next table.

Connection state consideration appears to be useful in the FORWARD chain, not in the PREROUTING or POSTROUTING, so use it in the FORWARD filter or FORWARD mangle tables.

Additional note: state match module is obsolete and removed from the kernel. Actual match is implemented with the conntrack module. In my opinion, it is better to use it explicitely, so better always use -m conntrack --ctstate ... rather that -m state.