I believe I know the answer to my dilemma, but wanted to pick the NetworkStackExchange community brain.
We currently perform Twice NAT'ing for a affiliate we have a peer exchange point with using a Palo Alto security device, their device is a straight leg into a router. We do Twice NAT'ing to make it easier for them to distribute a single route-able subnet with in their network to reach our network and vice versa. The issue of overlapping subnets is coming up, and we are currently having issues with because we are using a single security device to perform the NAT'ing. I believe the issue is because the security device makes it's routing decision pre-NAT, based on the documentation found in Palo Alto's Understanding and Configuring NAT.
My question is the only way around overlapping IPs is to do source NAT'ing for each side on two devices?
So if I initiate a ICMP ping like the depiction below I see the echo reply being routed back out the same interface it came in on.