Creo que te entiendo.. Se me ocurre que puedes guardar el ultimo id ingresado en una tabla temporal y ese id es al que le vas a sumar.
Por ejemplo, vamos a comenzar con un primer registro en la tabla que va a hacer 1, o tambien lo puedes obtener con mysql_insert_id(); la primera vez, luego guardas ese valor en la tabla temporal. Cuando vayas a ingresar el segundo registro busca el de la tabla tamporal y le sumas 1, lo guardas en la temporal, y asi sucesivamente, de manera que si eliminas no afectara los id.
Espero que te ayude..
Bye