Asymmetrical routing in general does not work with NAT gateways and stateful inspection firewalls. (It might even break packet fragmentation/reassembly.) This has to be taken into consideration when designing gateway failover solutions. Dynamic routing protocols might help on occasion, especially with static 1:1 mappings.
This particular potential problem can be overcome if the routers share the same NAT configuration and rapidly and constantly exchange state information to ensure a failsafe backup for each other. Nevertheless, a busy enterprise gateway most likely will still lose some connections or drop packets during a short transitional switch-over phase.
OpenBSD's pf is the first integrated gateway/NAT engine of open-source character that has NAT and stateful inspection table synchronization under development (pfsync). The Cisco PIX Firewall offers a proprietary failover approach, and Cisco IOS routers are capable of dealing with stateful failover translation groups.
Note that stateful NAT (SNAT in Cisco lingo) enables continuous service for dynamically mapped NAT sessions and works with Hot Standby Router Protocol (HSRP). Occasionally, NAT gateways also provide DHCP services to internal network segments. A true redundancy architecture also requires mirroring/synchronizing of DHCP lease tables. This is possible with the ISC dhcpd.