Похоже, вы хотите представить службу из (например) сети 10.0.0.0/8 в другую сеть 10.0.0.0/8 через Интернет, с NAT, работающим на обоих концах.
Если ваш сетевой администратор не перенаправил определенные порты на ваш внутренний IP-адрес, вы не сможете получать входящие соединения от хостов за пределами локальной сети. Ваш хост должен инициировать все соединения за пределами локальной сети, чтобы любая связь происходила за пределами локальной сети. Так как это верно для обеих сторон, вы оба довольно застряли в этом отношении.
Есть одно исключение: если и вы, и другая сторона подключаетесь к сторонней службе VPN, которая будет туннелировать ваши подключения, тогда она может работать. OpenVPN может быть настроен таким образом на VPS или другом доступном месте - и ваш хост, и удаленный хост будут подключаться к экземпляру OpenVPN. Поскольку соединение, инициированное обоими узлами, существует с сервером VPN, и сервер VPN будет пересылать трафик между узлами (действующими в качестве маршрутизатора) в туннеле, вы можете затем принимать входящие соединения над туннельной, "виртуальной" сетью.
OpenVPN довольно легок, но требует определенных знаний для настройки (особенно если вы хотите использовать шифрование) и, очевидно, должен работать в отдельном месте, доступном для обоих хостов. Я не уверен, что что-то "под ключ", как Hamachi VPN, будет работать так же.
Я предлагаю OpenVPN, потому что он использует TCP или UDP, по вашему выбору. Также можно использовать сервер Windows (или Linux) с запущенными службами PPTP, если ни один из маршрутизаторов не блокирует исходящий трафик GRE. Не уверен, насколько важна настройка PPTP-сервера в Windows.