Muchas gracias eboy, pero no quiero mezclar mi empresa en los foros.
Yo te recomendaría Rackspace, además tienen acuerdos muy buenos con sw-soft para el soporte de Plesk. Estos son los mejores (para mi) en cuanto a manejados con Plesk, de hecho les tengo envídia!!
Algo más "normalito" es Interland, tendrás ayuda, pero has de estar atento de las actualizaciones (especialmente las de seguridad). El precio es bastante bueno.
Por debajo de esto no te recomiendo nada, puedes ahorrarte dinero, pero ganarás disgustos. Por cierto, si te pasas por el foro de sw-soft podrás ver otros usuarios que hablan de ese problema y de cómo solucionarlo:
http://forum.sw-soft.com
Edito para añadir un comentario: Cuando he dicho "Por debajo de esto no te recomiendo nada", me refiero a por debajo de Interland. Entre Interland y Rackspace estamos muchíiiisimas empresas. Desgraciadamente también hay mucho cara dura.