Problems with removing NAT from a network

[ML <ml () kenweb org>]

I've got a customer that is looking to multihome with upstreams in two 
POPs.  Currently they multihome in one POP and utilize a single edge 
router for some one to one NAT and some PAT for their users.

Before they turn up the BGP peer in the new POP I've advised them to 
abolish NAT once and for all in order to avoid issues with non-stateful 
NAT between network edges and possible asymmetric routing of their 
Internet traffic.

The PAT can be removed easily enough.  The tricky part is the one-one 
NAT. They have quite a few systems which have 1918 IPs which they claim 
"cannot be changed". At least not without some painful rebuilds of 
criticals systems which have these IPs deeply embedded in their configs.

Has anyone here had to fix this kind of problem before? Is there a 
solution that would allow NAT to offloaded to a smaller device hanging 
off each edge router that can communicate state between each other in 
case traffic is asymmetrically routed?