Ну если изнутри сетки нет проблем с подключением по 3389, а снаружи есть, то здесь только 2 варианта:
- неправильно настроенный проброс порта на роутере
- пров всеже блокирует порт, хоть и говорит что нет.
Как вариант можно проверить провайдера следующим образом:
Берем любую машину с XP pro и настроенным rdp и IP адресом роутера, подключаем вместо роутера (напрямую в интернет) и пробуем подключиться.

Если подключение состоится, то проблема в настройке роутера, иначе - провайдер...