A principal funcionalidade que você vai querer procurar na escolha de uma solução VPN é o 'UDP hole-punching'. Ele funciona coordenando (manualmente ou com um registro) o endereço IP, a origem e a porta de destino de ambas as extremidades do túnel VPN.
Supondo que os firewalls sejam stateful, quando um par envia um pacote para o outro par, ele abre temporariamente um furo (porta de origem) no firewall upstream projetado para o tráfego de retorno. Se o outro par segmentar esse buraco (porta de destino) com seus pacotes de negociação de VPN (e vice-versa), ele poderá estabelecer um túnel usando apenas permissões de saída, que geralmente são menos restritivas.
Uma busca rápida por um programa VPN com perfuração UDP apareceu no Campagnol VPN no sourceforge. Em uma inspeção superficial, acredito que isso atenderia às suas necessidades, embora seja necessário usar um servidor externo para registro. Tenho certeza de que há outros também.