Hay un monton de cosas que debes tomar en cuenta antes de mudarte, regularmente es un dolor de cabeza :D
Dentro de las primeras estan
- Optimiza tu MySql my.conf
- Activas Varnish o Nginx como cache http
- Probar Memcached u otro Cache de consultas y operaciones
- Monitorea tus aplicaciones/servidor, mientras mas sepas de ellas mejor
- Chequea el IO Wait quizas la velocidad de tu disco a nivel de IO esta al Limite
Dile a tu proveedor que te de muestras de el abuso y las posteas aqui, muchos podran ayudarte a ver que tan sinceras son.
Un Gran Abrazo