The NAT solution is really simple. You pick a NAT block for them to use, and they pick a NAT block for you to use. Each side applies the NATs for their own addresses using the NAT block provided by the peer. That way, you always talk with a block of addresses you know don't overlap with anything in our environment, they always talk with addresses which they know don't overlap with anything in their environment. Within the tunnel, it will be the addresses they selected for you and the addresses you selected for them, with no real addresses at all. Works for VPNs or WAN links, and keeps everything unambiguous.