Можно посмотреть:
http://www.gamedev.ru/code/forum/?id=128784&page=17
там есть рабочий пример на блице соединения nat-nat (используется STUN). Примерно также работают скайп, хамачи и т.д.
Если коротко: клиент1 и клиент2 за натом, им нужно узнать свои внешние ip и порты (для чего есть публичные сервисы STUN) и передать их друг-другу доступным способом (аська, web или др.). Далее клиенты посылают первые "стартовые" пакеты друг-другу, которые не пройдут, но "познакомят" свои наты с нужными ip:port. После чего уже можно слать все что угодно.
Такой канал будет жить до ближайшей паузы 20-30 сек, после такой паузы нат может забрать порт (время таймаута устанавливает провайдер).
Связь удивительно стабильная выходит, ни одного пакета не пропало в тестах, даже на gprs.