Fora de uma solução VPN, que é a melhor solução, obviamente.
Eu tive clientes no passado que insistem na melhor segurança possível sem dinheiro, LOL, parece redicules eh.
De qualquer forma, além de senhas muito strongs, como você diz, altere o número da porta que o Terminal Server atende. Todo mundo sabe que a porta 3389 é o Terminal Server, mude-o para algo obscuro, você pode fechar essa porta no firewall e abrir a nova, torná-la algo muito alto no intervalo de portas, como 9000, para não ser digitalizada durante uma simples varredura de porta de fora da sua rede.
Depois disso, clique aqui link e execute o teste, você não verá a porta dos servidores de terminal no lista, esperamos que você não veja nada, exceto o seu servidor de email, se você tiver um