multiplexing traffic

[schmurfy]

Hi,
I have a routing problem I can't firgure out how to solve, here is what I wish to have:

There are two routers, one running OpenBSD and the other one running Linux, the network represented on this graph are physical sites of a given company, the two on top belongs to company1 and the two at the bottom to company2.

My problem is how to link those sites together while keeping each company separated one from each other given that both companies can use the same network addresses as they wish (for example 192.168.0.0/24 may be used here by both sites on the right).

The problem get a little more complicated since we have limited control over the Linux router and the technologies we have available is restricted, we have ipip but not ipsec for example.

How this problem is usually solved ? I suppose I am not the first one to try something like that. I am interested to hear your solution even between two OpenBSD.

Edit: I also have acess to gre tunnels which can have a key fields to allow multiple tunnels with same src/dst, sadly the key fields is not implemented under OpenBSD...