I realize this thread is pretty old, but it's still relevant so I'll give my two cents.

If you're looking for a cheap VPS, I'd recommend following the LowEndBox blog. They seem to be a reliable source for posting cheap and low-end VPS'. For example, AlphaRacks currently has a deal on their 768MB/single core VPS for $11 USD a year, and they accept Bitcoin. Link to the LowEndBox article about it.