Lowendbox
Worth having a look at lowendbox.com
I've worked with a few "companies" that have absolutely minimal budget so have bounced around quite a few of these cheap VPS providers. Experience on the whole is largely very good. Main uses... DNS, distributed mail relay clusters, reverse proxy caches, database replicas, backup boxes, and generally being able to distribute workloads across several providers.