C'est un hébergement mutualisé ? Si oui, il y a des chances que ton problème de performances "aléatoire" soit lié à une surcharge de la machine, quoiqu'en dise ton hébergeur. De toute façon, sur les mutu c'est toujours pareil: quand tu appelle le support, tout va bien, aucun problème, tout roule, on a rien remarqué.
Si c'est un VPS "Classic" de chez OVH, condoléances, ta VM (Open VZ) n'est pas protégée contre les autres. Bouge vers une offre VPS Cloud.
Si c'est un VPS ou un dédié, vérifie que MySQL est correctement configuré.