Оптимизирал ли си таблиците? Пусни едно OPTIMIZE TABLE <table>;

http://dev.mysql.com/doc/refman/4.1/en/optimize-table.html

По принцип като триеш записи в таблици с текстови полета с променлива дължина, мястото не се освобождава автоматично а се използва при последващи INSERT-и.