Sim, sua solução de usar uma VPN é a resposta, mas você precisará encontrar um provedor que forneça um endpoint válido na VPN. Eles existem - eu pesquisei IP estático no vpn e encontrei alguns.
Pensando nisso um pouco mais, se você tiver as habilidades, você pode alugar um LEB (Low End Box = Servidor Virtual de baixo nível) e configurá-lo como um endpoint para sua VPN, ou então ter 2 conexões VPN para esse ponto. LEB para que suas máquinas possam se ver ou redirecionar a partir da VPN para o seu endereço IP RFC1918 conhecido diretamente - essa pode ser uma solução mais barata.