codice:
OPTIMIZE TABLE should be used if you have deleted a large part of a table or if you have
made many changes to a table with variable-length rows (tables that have VARCHAR,
VARBINARY, BLOB, or TEXT columns).
Deleted rows are maintained in a linked list and 
subsequent INSERT operations reuse old row positions.
You can use OPTIMIZE TABLE to reclaim the unused space and to defragment the data file.
In pratica, secondo me, non ti devi preoccupare.
Oppure dopo ogni cancellazione usi OPTIMIZE TABLE, ma l'id cancellato comunque non sarà recuperato.