Ктони-будь сталкивался с подобной проблемой, поиск по таблице сразу отшибает, база начинает жестоко глючить. Были случаи когда происходила потеря данных, было 20 000 строк, пару манипуляий с попыткой добавить новую запись и строк уже 17 000 и так на уменьшение.
Как вариант перекопировываю две таблицы целиком, сношу глюченые таблица и заманяю их вновь созданными, но это не вариант. Т.к. рано или поздно все повторяется. Поврежденные строки нельзя удалить, т.к. вылетает ошибка толи "Неправильный индекс", то ли "Несуществующий индекс"
Ктонить знает как можно решить эту проблему