Eu tenho exatamente o mesmo problema e não consegui encontrar uma solução por muito tempo.
O problema para mim é o "Xbox Live Networking Service". Mesmo em uma instalação limpa do Windows 10, a VPN funcionaria uma ou duas vezes e depois ficaria presa novamente.
Eu posso replicar o problema 100% iniciando o "Xbox Live Networking Service", quando ele é iniciado, não consigo acessar nenhuma VPN, quando a VPN pára, ela funciona perfeitamente.
Etapas para resolver:
1. Serviços Abertos (services.msc)
2. Role para baixo até "Xbox Live Networking Service"
3. Se o serviço estiver em execução, selecione-o e clique em Parar
4. VPN agora deve funcionar, não há necessidade de reiniciar etc
Eu relatei isso à Microsoft recentemente. É reproduzível mesmo em instalações limpas.