If you are looking at the other extreme - i.e extremely cheap VPS - check out http://lowendbox.com/ - you can get some pretty decent ones for $10 a year
Remember that you get what you pay for. I had a very cheap VPS ($1.61 per month) for a few months until it went down. I got an email 2 days later saying that the hosting company was being kicked out of their data center because one of their clients had been the victim of a DDoS attack, and they were in the process of overnight shipping all of their servers across the country to a new data center. Luckily I was just hosting some non-critical personal projects, so I wasn't adversely affected. In the end they were down for 5 days, which under the circumstances is actually pretty impressive.
I've heard about those cheap VPS that simply disappear from existence.
Unless is something completely disposable, I'd rather pay 5$/month and go with something like Digital Ocean that I can be pretty sure will last for years.
Most are kiddie hosts who rent a dedi for a few months, install OVZ, and get on the front page the next day. That's what happens when you go with ColoCrossing - instant post to LEB to you.
Linode, AWS, HostVirtual, Digital Ocean... Just anything but a LowEndBox VPS.