Existem muitos fatores que podem ser a causa disso.
O resolvedor lento não deve ter impacto se você puder avaliar as consultas por conta própria. No entanto, um resolvedor lento pode definitivamente ter um efeito ao se conectar ao servidor - se os usuários tiverem acesso com base no nome do host ao qual se conectam. O MySQL também possui uma opção para registrar o nome do host das conexões.
O relatório mysql não diz muito sobre os índices. O que eu costumo fazer quando vejo isso acontecendo, é que eu pego uma das consultas que demoram muito tempo e corro EXPLAIN nela. Se ele não usar nenhum índice e precisar fazer uma varredura completa na tabela, verifico se posso adicionar um índice que o torne mais rápido. Eu vi índices desaparecem por acidente antes (alguém apagou por acidente, um script de atualização excluiu e não colocou de volta depois, ou similar).
O servidor pode estar sobrecarregado de várias formas:
- O que sua métrica da CPU diz? Está preso no IOWait, na hora do sistema, na hora do usuário ou está realmente inativo?
- Dependendo do banco de dados, pode ser um cache de consultas frias que precisa de algum tempo para se aquecer após a reinicialização do servidor. Isso é improvável se os dados mudarem muito - mas pode acontecer se for usado principalmente para pesquisas.
Também pode ser uma série de consultas que bloqueiam a tabela, impedindo que as pesquisas ocorram em aproximadamente 10 segundos por vez. Você pode obter informações sobre isso se registrar consultas lentas em um arquivo.
Poderia ser um bug no MySQL. Há um fardo muito pesado em provar isso, mas acontece.
Você precisa de muito mais dados para descobrir a causa disso. Você precisa de métricas de CPU, memória, métricas do MySQL e tal. Posso sugerir uma ferramenta de monitoramento como o Munin? Existe um plugin MySQL muito bom que lhe dará dados interessantes como acontece.