Windows as a requirement to run a VPN server seems like a lot of overhead. There are many linux based vpn server packages which would lead to being much cheaper to rent a linux server.
Anyway, when I had windows servers in the USA I used RackShack, which became EV1Servers, which became ThePlanet.
You should also look at ServerBeach.
There is a pretty pants company who may be cheap and reliable enough for your needs... FDCServers.
WebHostingTalk may be a better place to ask these questions.
Sadly Tom I think that guy was a spammer, he made a few random question topics and never responds. Plus his IP address looks like a temporary bot proxy.