Sounds like you want to expose a service from a (for example) 10.0.0.0/8 network to another 10.0.0.0/8 network across the internet, with NAT working on both ends.
Unless your network administrator has forwarded specific ports to your internal IP, there is no way you are able to receive incoming connections from hosts outside the LAN. Your host must initiate all connections outside of the LAN for any communication to take place outside of the LAN. Since this is true on both sides, you both are pretty stuck in this regard.
There is one exception: if both you and the other party connect to a third-party VPN service, that will tunnel your connections, then it can work. OpenVPN can be setup this way on a VPS or other accessible location - both your host and the remote host will connect to the OpenVPN instance. Since a connection, initiated by both hosts, exists to the VPN server, and the VPN server will be forwarding traffic between hosts (acting as a router) within the tunnel, you can then accept incoming connections OVER the tunneled, "virtual" network.
OpenVPN is fairly lightweight but it requires a some knowledge to setup (especially if you want to use encryption), and obviously needs to be running in a separate location accessible to both hosts. I'm not sure if something "turnkey" like Hamachi VPN will work in the same way.
I suggest OpenVPN because it uses either TCP or UDP, at your option. A Windows (or Linux) server with PPTP services running could also be used, if either router aren't perchance blocking outgoing GRE traffic. Not sure how involved PPTP server setup is on Windows.