devi usare un gestore di 'buchi'... la prima cosa che mi viene in mente e' di fare un ciclo di SELECT per ogni id: se l'id non c'e', sei di fronte a un buco. pero' risultera' lento se hai migliaia di record e il tuo buco e' verso il fondo.
Oppure creare una tabella di id cancellati, da cui andare a pescare i nuovi id