Guarda todas las ID en un array, después generas un nuevo ID con el rango de items dentro del array, cuando salga el nuevo ID tomas el valor del indice indicado, luego borras el indice y vuelves a acomodar los items en el array, así cada vez generas un ID con el numero exacto de items dentro del array y así te aseguras que no se repita y que el ID generado salga rapidamente, para que se entienda mejor...
Código PHP:
Ver original<?php
//obtienes TODOS los registros de tu base de datos la 1ra vez y los guardas en un array, este después
//lo puedes guardar en una sesión o en un archivo, yo que se...
$array = array(1,2,3,4,5,6,7,8,9,0);
$valor = $array[$indice];
//guardas el array con el item borrado...