Can't connect to VPN any longer on Windows 8.1

I'm not sure what caused it to stop working, but I cannot connect to my VPN connections that I used to be able to connect to before. I get this error (in Event Viewer's Application logs from RasClient):

The user SYSTEM dialed a connection named Virtual Private Network which has failed. The error code returned on failure is 628.

The current VPN type setup (Properties -> Security -> Type of VPN) uses L2TP/IPSec with a pre-shared key. When I set the Security to automatic (which used to also work before), I see this error instead:

The user SYSTEM dialed a connection named Virtual Private Network which has failed. The error code returned on failure is 720.

In the System log, additionally, there is (from RasSstp):

The initial Secure Socket Tunneling Protocol request could not be successfully sent to the server. This can be due to network connectivity issues or certificate (trust) issues. The detailed error message is provided below. Correct the problem and try again.

The remote computer refused the network connection.

I tried tracing the RAS layer using:

netsh ras set tracing * enable

...I then attempt the connection again...

netsh ras set tracing * disable

The logs contained a single file which was the most helpful at telling me there was a problem, EXPLORER_RASAPI32.LOG...but it wasn't helpful at telling me exactly what that problem was as far as I can tell:

[10236] 07-22 00:09:01:496: WaitForDialMachineEvent: Unblock i=1, h=0x22ec4250
[10236] 07-22 00:09:01:496: setting rasman state to 6
[10236] 07-22 00:09:01:496: NotifyCaller called for hPort:1
[10236] 07-22 00:09:01:496: NotifyCaller(nt=0x2,su=1,s=6,e=0,xe=0)...
[10236] 07-22 00:09:01:496: NotifyCaller done (dwNotifyResult=1)
[10236] 07-22 00:09:01:496: RASCS_AuthNotify
[10236] 07-22 00:09:01:496: RasProtocolGetInfo...
[10236] 07-22 00:09:01:496: RasProtocolGetInfo done(0), msgId=1
[10236] 07-22 00:09:01:496: RasDialMachine errors=720,0
[10236] 07-22 00:09:01:496: RasDialMachine: SignalDone: prasconncb=0x22ec4240
[10236] 07-22 00:09:01:496: SignalDone: pOverlapped=0x22ec42f0

For sure the problem resides just on this machine alone, as I tried tethering to my iPhone's LTE connection and got the same issue. I also tried this exact same connection on another PC on my network and it worked just fine (so its definitely not the router - which I checked a multitude of times). Doing a bunch of searching over the past few days, I must have tried everything I came across.

• Nothing from here fixed the issue.
• I tried checking to see if I had any DNS issues, so I tried connecting directly to the VPN machine's IP and it worked just fine. Also, pinging it works fine.
• I tried pinging localhost, my local IP, my router's IP, and my VPN's IP, and all seem to work just fine.
• I fixed any improperly functioning WAN Miniport issues in Device Manager by updating them to other drivers and uninstalling them so that they refresh properly in a following boot to their correct, and working drivers (which, there were problems but now all devices in Device Manager are looking solid).
• I tried uninstalling and reinstalling any Network Adapter I could in Device Manager.
• I tried reinstalling my network drivers.
• I tried netsh int ip reset. I even used Process Explorer from Sysinternals to grant registry access permissions for this command to not fail in some cases due to access denied issues.
• I tried netsh winsock reset.
• I tried sfc /scannow. It found some corruptions but fixed them.
• I tried Dism /Online /Cleanup-Image /RestoreHealth. It also found some corruptions but fixed them.
• I tried Remove-NetIPAddress in PowerShell.
• I tried rebooting my router.
• I tried obtaining a different local IP address from my router for this problematic machine but that didn't help.
• I tried disabling my BitDefender antivirus.
• I tried disabling my BitDefender firewall.
• I tried deleting and re-adding the VPN connection about a million times.
• I tried uninstalling my BitDefender antivirus/firewall and repeating all of the above.
• I ran BitDefender's Rescue Disk from a boot disk to check for kernel malware and it didn't find anything (I also use Secure Boot so I doubt any malware would reside in hardware).
• I tried using OpenVPN but this did not work for me and I found SChannel errors in Event Viewer, here is an example:

A fatal alert was generated and sent to the remote endpoint. This may result in termination of the connection. The TLS protocol defined fatal error code is 43. The Windows SChannel error state is 552.

The certificate received from the remote server has not validated correctly. The error code is 0x80092013. The SSL connection request has failed. The attached data contains the server certificate.

My Windows 8.1 is x64 and fully updated as of right now. What else can I try, and how else can I troubleshoot this bizarre issue? From the looks of the logs I can't help but wonder if perhaps my certificate store has become corrupted somehow. Is there any way I can try restoring it?

Note: The guidance I provide here, if you intend to follow any of it you do it at your own risk and I take no responsibility for your actions. The first thing I needed to do was...unlike how most articles I found online say that I need to ONLY remove the WAN Miniport drivers under Device Manager's Network Adapters, I actually had to remove ALL Network Adapters under there. Maybe its overkill, I dunno, its the only thing that worked for me.

How to Achieve Removal of All Network Adapters in Windows 8.1

• You need to update each one individually to an arbitrary kernel driver. I used some random Bluetooth driver at the top of the Microsoft drivers list.
• You need to right click the newly updated driver and Uninstall it.

Sometimes, you may find you have issues uninstalling these drivers. One issue I had was blue-screens that would happen every time I tried to uninstall a particular one of them. However, I found these tools a huge help (again, use them at your own risk). Once I followed the guide and ran WAN Miniport Repair Tool Version 2 and then ran the WAN Miniport Installer, no more bluescreens, just that it installs more devices under Network Adapters, so now you need to go through a few reboots and uninstall these drivers a few times, over and over again. Its painful and time consuming, but worth it.

If you hit the Windows key and type services.msc, you will find, in Windows 8.1, a neat little service called Remote Access Connection Manager. This will enable some of the Miniport adapters for you. Otherwise, if they are not enabled and are hidden in Device Manager, you will not be able to update them as they will not take on another arbitrary kernel driver. Start and Stop this service at will in order to enable these drivers for updates.

Make sure to remove all drivers. Once you are done removing them all, start the Remote Access Connection Manager service again and see if you have any more faulty drivers. This time, just look for the yellow warning icons and update only the ones with these icons. Repeat this process (keep restarting the Remote Access Connection Manager until all of them no longer have the icons).

This service should only be starting the Miniport drivers, so all you should have now is the Miniport drivers and the RAS Async Adapter. I also updated and uninstalled the RAS Async Adapter at some point. I am not sure if that also required me to start a different service or not anymore (the other service was Remote Access Auto Connection Manager).

At this point, with only Miniport adapters showing, I rebooted, one last god damn time, and it worked. I was so happy I could cry (but didn't - I would never).

I had to, by the way, start hard rebooting to make things less time consuming by holding the power button, and pressing CTRL+ALT+DELETE when the "Please wait" screen in Windows came up to bypass it from going into that annoying startup options window.