primero que nada, recuerda que el espacio y transferencia mensual asignada a tu cuenta por tu proveedor hosting, no tiene nada que ver con el consumo de recursos de el servidor, en vista de que a veces usamos hosting compartidos, los recursos de el servidor son proporcionales para todos los clientes, asi como dices si tu cuenta excede las consultas mysql es probable que tu proveedor te haya reportado uso excesivo de recursos de el servidor, y si es cierto pues tener un VPS o un dedicado es buena opcion, a no ser que el server donde estas alojado tenga muchas paginas web alojadas, eso haria que la tuya al consumir un tanto mas que otras cuentas, mate su server y te anden reclamando, pero siendo ya eso problema de tu proveedor cuando en realidad no requieres de un dedicado y puedes manejarlo bien desde otro proveedor hosting, espero me entiendas
en todo caso si persistes con la idea de un dedicado, si quieres garantia t recomiendo
http://www.theplanet.com y si quieres minimizar costos t recomiendo
http://www.limestonenetworks.com ambos muy buenos solo que el primero tiene mejor soporte y garantia
saludos