Oye, yo tuve un problema parecido que al borrar un registro por ejemplo si borras el registro 20 te queda 19 y luego 21, yo lo solucione de la siguiente forma, que cuando borre un registro tambien borre la columna completa de id que es la que contiene el AUTO_INCREMENT y luego que la vuelva a crear con las mismas propiedades que antes y por arte de magia vuelve a numerar todos los registros.
Aqui te dejo el codigo
Código PHP:
$quitar = "DELETE FROM `tu_tabla` WHERE `id` = '20'";
$quitar_index = "ALTER TABLE `tu_tabla` DROP id";
$poner_index = "ALTER TABLE `tu_tabla` ADD id INT NOT NULL AUTO_INCREMENT PRIMARY KEY FIRST";
mysql_query($quitar,$conectar);
mysql_query($quitar_index,$conectar);
mysql_query($poner_index,$conectar);
Si lo solucionas me dices ok, Suerte
Saludos