PPAУ меня так-же существует проблема с клиентами за NAT.
очень интересно посмотреть реализацию обхода через шлюз.
Если лицензия будет позволять интегрировать твой код в другую OpenSource программу
выкладывай на github свой движок.
Выкладывать пока нечего, есть версия 1.0, но как обычно к концу разработки стало понятно что все надо было сделать по-другому. Пока только готовлюсь, текучки много последнее время, никак не соберусь начать писать 2.0.

Конкретно по НАТам все просто:
Есть сервер в инете (теоретически в случае его отсутствия можно других клиентов назначать сервером и т.д., но мне это не актуально, сервер есть и не один).
Каждый клиент поддерживает соединение с сервером и знает свой адрес (IP:порт и MTU), чтобы узнать IP:порт просто посылает запрос серверу тот сообщает откуда пришло. C MTU посложнее: клиент устанавливает флаг запрета фрагментации и отправляет серверу несколько десятков пакетов разной длины, сервер сообщает какие дошли. MTU обычно в диапазоне 1372-1472 (это без заголовков, т.е. сколько полезных байт может быть в пакете).

Клиента А хочет связаться с Б.
A: посылает запрос на соединение (MSG_CONNECT) через сервер, в запросе указан адрес А
Сервер: пересылает Б или отвечает что Б отсутствует.
Б: Получает MSG_CONNECT, отправляет А подтверждение (MSG_COMMIT), в нем указан адрес Б. Отправка через сервер.
А: получает MSG_COMMIT
Теперь у обоих есть адреса друг-друга.

Теперь как происходит "пробитие" НАТов. Встречный трехшаговый пинг:
Клиент получивший адрес второго посылает MSG_PING на этот адрес. Получивший MSG_PING отправляет MSG_PONG. Получивший MSG_PONG отправляет MSG_PUNG.
Если приходит MSG_PONG или MSG_PUNG связь со вторым считается установленной.
Если ответ не приходит, то через 100 мс отправляется второй MSG_PING, через 200 мс третий. Еще через 200 мс делается вывод что связь установить невозможно.

Максимальный размер пакета для обмена - наименьшее из двух MTU. Пакеты MSG_PING, MSG_PONG, MSG_PUNG имеют максимальный размер.

Т.е. в реале обычно получается так:
Б: получил MSG_CONNECT
Б: отправил MSG_PING
Роутер Б: ожидает пакеты с адреса А
Роутер А: убил входящий MSG_PING
А: получил MSG_COMMIT
А: отправил MSG_PING
Роутер А: ожидает пакеты с адреса Б
Роутер Б: пропустил входящий MSG_PING
Б: получил MSG_PING
Б: отправил MSG_PONG
А: получил MSG_PONG перешел в состояние связь с Б установлена
А: отправил MSG_PUNG
Б: получил MSG_PUNG перешел в состояние связь с А установлена

Тут А готов раньше Б и начинает слать полезную инфу, если Б не готов, то отвечает через сервер.
На самом деле А начинает слать инфу через сервер как только получил MSG_COMMIT, а в процессе переключается на прямую передачу. Если на момент переключения вся инфа уже отправлена, то повторяет отправку на адрес Б. Т.е. цель как можно быстрее доставить всю инфу до Б.

Если А и Б в локалке за общим роутером, но некоторые роутеры их не соединят, просто рубят такие пакеты. Поэтому вместе с внешним адресом клиент сообщает свои локальные IP:порт, вторая сторона по той же схеме их пингует если есть совпадение по маске.

Еще учти такой момент: если ты открыл случайный порт, то брандмауэр виндовса через минуту перестает пропускать входящие пакеты с адреса, это при условии что в течении минуты не было приемов/отправок на этот адрес. Что делают роутеры - не изучал. Минуту точно ждут.
Поэтому либо периодически пинговать либо через минуту неактивности считать связь разорванной.