Data Center Failover

So the NAT that you are doing on your external firewalls, are you just doing destination NAT or also source NAT? If both, then the solution can be fairly easy. Just advertise the private NAT address space across the tunnel between sites so the firewalls know to push the traffic across to the other site to route back out to the Internet.

If just destination NAT, then you may need some kind of conditional route advertisement from your external router to your firewall. The logic of which would be if the BGP session with your ISP is up on your router (receiving default route or some other monitored route), then advertise the default route to your firewall. Do you already have a routing protocol setup between your router and firewall by chance?