IlyaEvseev, там по первой ссылке написано на счет DELETE QUICK, что даже после добавления новых данных пропуск в индексе останется, пока не будет выполнена команда OPTIMIZE TABLE, это касается таблиц с AUTO_INCREMENT колонкой.
AmdY, все нормально с таблицами, я же выше написал Вам, что на двух компьютерах одно и тоже. Может быть тормозов быть и не должно, если бы все поля были числовыми и без индексов, а здесь каждое поле с текстом по 1 кб.