MySql автоинкремент не учитывает удаленные id элементы

Вы столкнулись с некоторыми классическими проблемами, которые я по-быстрому опишу (и, возможно, у кого-то будет время расписать подробнее):

Автоматический инкремент продолжает свою работу с последнего значения, оставляя зазоры в удаленных значениях

Это абсолютно нормально. Стоит подавить внутреннего перфекциониста и оставить зазоры как есть. Ничего страшного в этом не будет, диапазона значений стандартного int хватит с головой на любой проетк, кроме визуального дискомфорта тех немногих, которые будут отслеживать ID в адресной строке, это ничего не принесет.

В проекте требуется хранить список ссылок на сущности, поэтому я храню их в виде строки значений, разделенных запятой

Такой подход не даст вам нормально пользоваться реляционной БД. Правильным подходом в данном случае будет завести новую таблицу, в которой описывать связи.

Неправильно:

TABLE students
id | first_name | last_name
1  | Vasya      | Pupkin
2  | Vitaliy    | Merkushev
TABLE teachers
id | first_name | last_name | students
1  | L'enfant   | Terrible  | '1,2'

Правильно:

TABLE students
id | first_name | last_name
1  | Vasya      | Pupkin
2  | Vitaliy    | Merkushev
TABLE teachers
id | first_name | last_name
1  | L'enfant   | Terrible 
TABLE teacher_students # таблица связей, которая описывает, какие именно студенты обучаются
teacher_id | student_id
1          | 1
1          | 2
# Кто учится у конкретного преподавателя?
SELECT students.* FROM teacher_students
INNER JOIN students ON teacher_students.student_id = students.id
WHERE teacher_id = 1

Формально это описывается т.н. нормальными формами БД, про которые вы можете прочитать в википедии

Мне требуется обновлять ссылки на сущности по мере изменения их идентификаторов

Специально для этого был придуман механизм внешних ключей (foreign key), который позволяет производить базовый набор действий при изменении связанной сущности, например, запрещать удалять преподавателя, пока у него есть студенты, или наоборот, удалять запись о связи в случае удаления студента.

Логика автоинкремента на движке MyISAM следующая

• при запуске сервера найти максимальный id в таблице и запомнить его
• при вставке новой записи, увеличить сохраненное значение на 1 и вставить

таким образом, Ваша ситуация будет проявляться только при перезапуске сервера. Чтобы обойти этот механизм, добавьте вспомогательную таблицу с одним автоинкрементным столбцом, а в своей таблице автоинкремент уберите. Тогда вставка новой записи будет выглядеть следующим образом

INSERT INTO gen (id) VALUES (NULL);
INSERT INTO mytable (id, .....) VALUES (LAST_INSERT_ID(), ......);

А удалять записи Вы будете только из основной таблицы.

Периодически, вспомогательную таблицу можно подчищать

DELETE FROM gen HAVING id < MAX(id);

Здесь ответ на ваш вопрос: http://stackoverflow.com/questions/3718229/stop-mysql-reusing-auto-increment-ids. В двух словах: в этом случае просто откажитесь от использовать автоинкремента и храните в отдельной таблице последнее значение для ключа, изменяя его при добавлении новых данных.