Hay muchas opciones, si no te choca entrar por ssh y hacer el trabajo tu mismo. Tengo buenas referencias de
http://www.linode.com/, tambien puedes usar Amazon EC2 (gratis 1 año)
http://aws.amazon.com/es/free/.
Otro muy buen proveedor es
http://www.rackspace.com/, y con azure me ha ido bien. Basicamente Linode+RackSpace tiene mejor soporte que los proveedores de cloud...