de mi experiencia en vps te recomiendo leaseweb,es el que uso actualmente, tiene paquetes desde los 7 euros mensuales,aun que hay un descuento,si contratas por un año,hace poco hicieron un upgrade a sus servidores y lo minimo que ofertan es 1gb de ram ofrece windows y linux, el soporte es en ingles y responden mas o menos rápido,aun que aclaro los vps no son autoadministrados
puedes ver aqui los paquetes por si te interesa
http://www.leaseweb.com/en/cloud-hosting/virtual-server