Qual é o tamanho do seu banco de dados? Qual mecanismo de armazenamento você está usando? São principalmente dois: myIsam (o padrão) e InnoDB. myIsam não manipula muito bem a gravação concorrente, e o atraso pode ocorrer durante a inserção / atualização de linhas.
Se você estiver usando myIsam, você também pode experimentar o myisamchk, descrito aqui: link
Você provavelmente desejará usar a opção -d para reunir informações sobre suas tabelas antes de executar a instrução OPTIMIZE.
Os arquivos do banco de dados também podem ser hospedados em um caminho de rede ou em uma unidade falsa. No último caso, verifique o seu syslog em busca de um erro na unidade.