Barrapunto

Si que esté en Europa es un requisito:

Linode: 512MB RAM, 16GB disco, TX 200GB/mes, 19.95USD/mes (14,28 €/mes -al cambio de 1,3979 USD por €-), datacenter en Londres, permite distribuciones de 64 y también de 32 bits (para aprovechar mejor la memoria).

Dudo que necesitéis más de eso, aún cuando multipliquéis por cuatro el tráfico (ni por CPU, RAM, ni ancho de banda). El rendimiento de los VPSs de Linode a menudo es mejor que los *dedicados* de otros proveedores (especialmente en lo referente al ancho de banda, sin contar con no tener que pagar un *pastón* por la posibilidad de que alguien esté en el datacenter para que le digas por teléfono que le haga un reset a la máquina, y demás temas manuales -que se reducen a prácticamente 0 con los VPSs-. En mi opinión, para montar un chiringuito con hardware dedicado hay que ser un descerebrado, o que te sobre la pasta y las horas de sueño.

Alternativas a Linode: European alternative to Linode? (self.programming) [reddit.com]

Entra en http://www.lowendbox.com/ [lowendbox.com] que ponen ofertas de VPS :)
De todas maneras, cuidadín con los VPS que ponen ahí, que hay algunos que no son de fiar.

Mira a ver éstos: http://www.slicehost.com/ [slicehost.com] Tenemos un "slice" en el curro y no van mal. Aunque lo dan con lo mínimo, mínimo, mínimo en accesos xD

Linode o slicehost. Linode ofrece mas por el mismo precio pero el soporte de slicehost es de lo mejor que he visto.

Tambien puedes probar las microinstancias de EC2 o la cloud de Rackspace [rackspacecloud.com]

Has mirado RPS (Si no me equivoco tienes tu propia maquina y procesador, el espacio de HD es un "Disco" que no esta en la propia maquina). Yo he visto en: http://www.ovh.es/productos/productos_rps.xml [www.ovh.es] Parecen precios muy competitivos. Supongo que su datacenter estará en Francia (no se si tendrá en España). Podrías contactar con ellos para preguntar donde lo tienes, explicarle tus necesidades y a lo mejor te recomiendan el correcto. Sobre la empresa no tengo información.

Efectivamente. Mi VPS Debian bajo de 280Mb de memoria a 100Mb en 5 minutos ajustando la configuración de apache/mysql.