Сделать EXPLAIN по выполняемым запросам (из можно найти, настроив mysql slow log), прочитать вывод и предпринять шаги и действия согласно найденной информации.
А еще, подозреваю у вас там есть поле типа TEXT, из-за которых индексация перестает часто работать) вернее начинает работать через диск.