Clientes OpenVPN podem ser executados como um Deamon do Windows por trás do NAT. O servidor, no entanto, precisará de alguma configuração adicional para trabalhar com o NAT. Mas isso não deve ser um problema.
Veja mais informações aqui: Como executar o OpenVPN como um serviço do Windows
Como você precisa executar seu próprio servidor para o OpenVPN, pagar por ele está fora de questão.