Друзья спасибо всем за советы и мнения! Очень рад что тема нашла отклик. Надеюсь все написанное пригодится не только мне.
Самостоятельно пришел к следующему решению:
Решил не возиться пока с Linux ввиду недостатка опыта работы с оным, а взял в Финляндии виртуалку с Windows Server 2016 за 3$ в мес. На арендованном забугорном сервере поднята SoftEther VPN Server с SecureNAT. Виртуальная машина с сервером терминалов, расположенная в РФ коннектится через L2TP VPN к этому серверу. А юзеры терминалов коннетятся к нему же таким же образом через L2TP VPN.
Получилась схема: Клиент RDP через VPN -> Сервер в Финляндии (SoftEtherVPN Server) > VPN до сервера в РФ.
Приятно порадовала скорость подключения, лагов нет, качество согласно индикатору RDP 8.1 хорошее.
Более того, покуда в свойствах VPN подключения российского сервера ставим галочку шлюза удаленной сети, удалось дать пользователям RDP сервера доступ в сеть через тот же Финский сервак. Тепеперь у наших RDP юзеров в офисе на сервере терминалов есть еще и интернет, который так же анонимизирован насколько возможно (финский IP).
Всем спасибо!