Yo recomiendo:
www.tektonic.net VPS americanos, muy baratos y muy buenos, 0 problemas con ellos, soporte las 24 horas
www.ovh.es Dedicados casi regalados, y vps a precios muy buenos tambien, dificil que encuentres mejores precios
www.server4you.com ,precios de ganga, dedicados desde 30 dolares anuales, tuve uno con ellos y siempre me funciono bien, aunque solo lo use para hacer experimentos.
A caray, no me fije que lo pedias completamente administrado, y por que necesitas un servidor propio?, no te vendria mejor un hosting compartido con ip privada?