VPN Error 718 - all users all of a sudden

Indeed, normally there is at least one remote access policy enabled. The passthru tends to be the default which I agree it is not very good to have but for quick certainty check may be worth. This include connecting from a local workstation for a first check so that the server config is alright (since no change) before trying to connect from a remote machine.

Nonetheless, I supposed this step thru check is done in order to surface more symptoms of the sudden 718 occurrence surge. It seems to allude to n/w changes in the infra if the config has not been changed or patch / revision push down is of non-existence.  Noted the older OS but worth quick glance on the troubleshooting steps - http://support.microsoft.com/kb/162847/EN-US

Those posted earlier is just inital quick checks. On the ip routes changing dynamically, you should notice it strange if tjis is first occurrence compared to past log, definitely something going on with some network changes. Better to confirm any tracert path or perimeter proxy has swapped isp due to patch for failover patching exercises etc.
 
As for the NPS,  it seems to be close to this if NPS has the similar list of event prior to having 718 coming.
http://social.technet.microsoft.com/Forums/windowsserver/en-US/b05fa484-af53-4154-88dd-04d5266f8068/vpn-errors-out-with-718