I've used Future Hosting http://www.futurehosting.com/ for a few years now, with two different VPS instances for $30/month each. Never had a problem, and if they did something like this I'd be shocked.