The typical solution to joining networks is to use a VPN, and if complete freedom of IP addressing is required a VPN with NAT is required. (This
example of a NAT/IPSec solution from the OpenBSD Journal describes the issue and one way of resolving it.)
As you have described your problem, I understand you have these constraints:
- IPSec cannot be used
- A NAT solution must be chosen that operates with the existing routers
My first thought is to wonder why there is a no-IPSec-on-Linux constraint, and who the idiot is at the partner company who made that decision for you.
But that doesn't solve the problem, and pointing out to your partner that IPSec has been available for many many years on Linux systems may only strain your new relationship. And, due to the NAT requirement, having their "technician" suddenly say yes to IPSec may not solve the problem -- there might be differences in IPSec/NAT implementations between their Linux and OpenBSD that limit integration.
My second thought is to just to hand them an OpenBSD router for use at the partner company, and ask them to route traffic destined for your network(s) through it. There are a number of possible topologies, including a separate ISP connection, placement between the Linux router and the ISP, or sharing the subnet between their router and their ISP.
If no physical investment can be made in linking your organizations together, and if IPSec is a non-starter for ... um ... political reasons, you and they must look for other possible solutions. Here are one or two VPN solutions that might work:
OpenSSH should be available on that Linux platform and it is part of OpenBSD. VPNs may be configured with "ssh -w". I've never tried to configure it with NAT at both ends, however, and if this is of interest, I recommend setting up a small laboratory to experiment. (Hint: virtual machines might be used.)
OpenVPN is a third party program that runs on both Linux and OpenBSD, and offers certain types of NAT translations which might fit your needs. I have not used OpenVPN in many years, and never used it to join gateway routers. As with the SSH VPN solution above, investigation and experimentation are recommended.