All' INSERT successivo alla cancellazione puoi dare tu il valore dell'ID in questa maniera:

Codice PHP:
SELECT MAX(campo_idFROM tabella 
Cosi facendo utilizzi sempre il valore sucessivo dell'ID, non lasciandone di inutilizzati...ovviamente cosi facendo il campo auto_increment diventa totalment einutile.