Действительно есть такой вопрос, но ни как не проблема! Причем с разными типами таблиц работает по разному! В конце концов есть такой вариант еще: после каждого удаления или перед вставкой, надо подсчитать что реже происходит выполняешь следующее:
ALTER TABLE tbl_name AUTO_INCREMENT = 1
Соответственно попробует начать индекс с 1 (единицы) но а на самом деле начнет с максимального значения + 1!
Но всеж надо FAQ повесить по MySQL! Загадочно, но по другим БД у людей такой вопрос не возникает, а вот с MySQL возникает! А ведь ответ прост - используй BIGINT!

CREATE TABLE my_table (
id BIGINT UNSIGNED NOT NULL AUTO_INCREMENT,
);

Такое значение может хранить в этих пределах:
The unsigned range is 0 to 18446744073709551615
Не хватит? Не уверен! :)