[Petya V4sechkin]

Sk1fj, наблюдается ли проблема в Безопасном режиме с загрузкой сетевых драйверов?
Сторонний криптопровайдер не установлен?

перепробовал всевозможные описанные методы

Перечислите, чтобы нам не повторяться.

Petya V4sechkin,

наблюдается ли проблема в Безопасном режиме с загрузкой сетевых драйверов? »

Да. Точно так же.

Сторонний криптопровайдер не установлен? »

Не очень понял о чем именно речь... Что-то типа TrueCrypt'a? Если да, то нет, ничего такого не установлено.
UPD: почитал что такое "криптопровайдер", теперь точно могу сказать, что такого в системе нет.

Перечислите, чтобы нам не повторяться. »

1. Чистка реестров (приведено ниже в ссылках) не помогла (на ПК и на серве).

2. Не помогло: это и это.

3. Также не помогло KB323497.

3. От начала до конца прочитано и изучено данное FAQ.

4. Замена сетевой карты не помогла.

[Petya V4sechkin]

Sk1fj, посмотрите в свойствах сетевого подключения, нет ли сторонних клиентов/протоколов.
Примеры:

My Fix: Simply uninstall the Link-Layer Topology (Mapper I/O Driver and Responder) protocols, as well as the QoS Packet Scheduler service (you can add them back again afterwards) in the Local Area Connection of the client machine (not the server/target). You must uninstall, not simply remove the checkmark next to the protocol or service.

I uninstalled the Sonicwall Global VPN client and the problem went away.

Finally, removing Citrix DNE Lightweight Filter service from my network adapter solved the problem for me.

перелопатил весь гугл

Поищите по английскому запросу: Because of an error in data encryption, this session will end.

Petya V4sechkin, в подключениях был только Eset personal firewall, я его на всякий случай грохнул, но это тоже не помогло. Вот как сейчас выглядят свойства (см. прикреп. файл).
По англ. запросу нашел несколько других методов, но и они не помогли.

Нашел еще вот что интересное (scr1.png).
Но при нажатии "Удалить" или "Изменить", получаем следующее (scr2.png).
P.S. естейственно, ничего другого не запущено, и не ребут не помог.

UPD: Удалилось после третьего ребута. RPD по прежнему не пашет

[Cool29]

Попробуйте поискать в гугле "альтернатива rdp клиенту windows"

Cool29, спасибо за совет.
В общем, начал пробовать устанавливать другие клиенты, в итоге дошло до того, что там ошибка в корне самих обновлений винды. Сейчас проблема в запуске средства обновления, выдает следующую ошибку. Пытаюсь разобраться.
Снёс все на ноль: откат до SP2, IE установка с нуля. Пока ничего не помогает.

Итог мучений: переустановка WinXP. Теперь все работает.
Восстановления, обновления и пр. танцы не помогли ни коем образом.
Всем спасибо, кто проявил интерес и желание помочь.