http://xakep.ru/54483/
В частности интересны будут последнии 2 пункта:
UDP-туннель между двумя NAT - сам не проверял
Автоматический проброс портов или Universal Plug and Play (UPnP) - очень хорошая технология, но не могу подсказать поддерживается ли она rdp сервером винды, думаю гугл скажет более точно . В идеале было бы найти софт, который может работать с роутером по этому протоколу. Сталкивался с тем, что на dlink-ах и tp-link`ах по умолчанию UPnP включён.

3й вариант, которым очень давно, но успешно пользовался - проброс портов через ssh сервер. Где-то поднимаем ssh, к нему на том компе, который за натом, поднимаем конект с пробросом локального 3389 на некий виртуальный на ssh сервере. Потом конектимся к нашему ssh любым rdp-клиентом на этот порт и он перенаправляет нас на комп, спрятанный за натом. Но это тот еще геморой в настройках. Помнится у меня пару суток чтения манов и гугленья ушло... Кстати в статье на хакере, этот путь тоже расписан