I've scoured the Internets for hours for a similar problem, but every other Vista VPN problem is slightly different from mine.
I'm a consultant and work on and off client sites. One particular client's network is severely locked down (can't VPN out, heavy Internet filtering), but I do have access to a "dirty" wireless network in the same building (it's actually a different ISP entirely). I switch between their wired network and wireless network (wired so I can RDP and use VSS on their network and wireless so I can VPN to my company's office for our VSS and Exchange for e-mail). I am not allowed to be connected to each simultaneously.
Here's the issue: Every time I switch from the wired connection to the "dirty" wireless connection, I lose the ability to connect to my office's VPN. It fails immediately with an 800 error. I'm convinced that it doesn't even send a single packet out before it fails. To make it work, I must reboot while disconnected from the wired network (ethernet cable unplugged), then connect to the wireless network after the machine boots back up, and then I'm able to connect to the VPN, but only on a fresh reboot like this.
EDIT: If I make a successful VPN connection while on the wireless network, and that wireless network flakes out, once it reconnects, the VPN will consistently fail to reconnect until I reboot.
Logoffs and relogging on doesn't change anything. Disabling and re-enabling or resetting the ethernet adapters doesn't fix anything. Renewing IPs, flushing DNS, setting static IPs.... none of it works. ONLY a reboot allows me in, and as soon as I connect to the wired network it all dies. I CAN reconnect to the wireless network without a reboot, just no VPN. This happened after SP1 as far as I can remember.
More interesting yet is that in Vista's Network and Sharing Center, of the three options ("All," "Dialup and VPN," and "Wireless") once I switch from the wired to the wireless network (no reboot), "Dialup and VPN" option disappears completely from that list. I have a shortcut to the VPN connection that I try to launch.
I have NO virus software even installed, and I have NO firewalls enabled whatsoever. I've looked through the diagnostic logs and there's nothing interesting in there -- no other errors except the 800 one the VPN dialog returns.
So, does anyone have any ideas? Anything I could try -- registry hacks, third-party VPN clients, anything?