Mysql tiene la funcion:
OPTIMIZE
<a href='ir.asp?http://www.mysql.com/doc/O/P/OPTIMIZE_TABLE.html' target='_blank'>http://www.mysql.com/doc/O/P/OPTIMIZE_TA...</a>
Con esta funcion se reorganiza el indice de una tabla (caso tipico como el tuyo que borrastes uno o varios registros de una tabla).
Prueba la funcion y nos comentas ..
Un saludo,