Eu procuraria o Logmein Hamachi. É uma conexão VPN segura que possui algumas opções diferentes; Gateway, Malha e Hub / Spoke.
Você pode ter um servidor inicial configurado como um gateway. A partir daí, você entrará no seu PC da Europa para este gateway. Como o Hamachi é multi-plataforma, não há problema com o Linux / Windows. Quando ingressar no Gateway, será como se você estivesse na mesma rede e tenha acesso a todos os recursos da rede.
Se esses computadores fizerem parte de um controlador de domínio, você poderá usar as Diretivas de Grupo para enviar o acesso RDP às máquinas. A partir daqui, você pode usar os endereços IP como faria normalmente, como se estivesse na rede. Se acontecer de você estar em um pool de ip da rede que é o mesmo que o pool de ip da rede do gateway, você notará que o gateway recebe um tipo diferente de endereço.
Por exemplo, se sua rede é 192.168.1.0 e a rede remota também é 192.168.1.0, então você notará que seu gateway será algo bobo como 10.42.1.0. A partir daqui você pode usar 10.42.1.x onde x é o último conjunto do IP do computador. Então, se você tivesse dois computadores que você precisava acessar e seus IPs são 192.168.1.100 e 192.168.1.101, então você usaria 10.42.1.100 e 10.42.1.101.
[RE seu comentário]
Como eles fazem um pouco da configuração inicial, você pode fazer com que eles enviem por e-mail o endereço IP do computador. Usando a sugestão acima, você nem precisa das sessões remotas do Logmein, pois o gateway Hamachi lhe dará acesso imediato à sua rede.