Luego de borrar un record, ejecutas algo como:
Código PHP:
$count = mysql_num_rows(mysql_query("SELECT id FROM tabla"));
mysql_query("ALTER TABLE tabla AUTO_INCREMENT = ". $count + 1);
También podrías usar COUNT() en la consulta y así evitar usar mysql_num_rows
Desgraciadamente, eso solo serviría si el record que eliminaste es el último.
No conozco (aun) una forma de reordernar todos los valores de una clave primaria de forma facil, a lo mejor otro si, yo de tener que hacerlo usaria un ciclo para actualizar cada ID incrementando por 1 el ID en cada actualizacion