Em uma situação de domínio, você pode usar um servidor Windows 2008 como um "gateway de serviços de terminal" que, em conjunto com um certificado SSL, pode ser usado para hospedar um gateway público através do qual é possível RDP para hosts do outro lado. Isso realmente não é tão difícil de fazer.
no entanto, como parece que você pretende fazer isso com vários clientes por trás de muitos tipos diferentes de firewalls, por que não instalar um gateway logmain hamachi em uma máquina em cada cliente e usar essa máquina como um gateway para acessar a rede você precisa alcançar. Eu fiz isso muitas vezes.
Tom