Pues te recomiendo
http://www.lowendbox.com/ ya que hay un catalogo bien amplio de empresas que ofrecen VPS a bajo precio. (Yo consegui el mio a 5$/mes). Pero claro si quieres un servicio más estable (conocido) te recomiendo rackspace, que es lo que usamos en el laburo.
/be