почему вы даже не пытаетесь повторно использовать user_ids (заполнение пробелов) - как вы думаете, у вас кончатся ключевые значения ??
create table users
(
user_id int unsigned not null auto_increment primary key,
...
)
engine=innodb;
int unsigned имеет возможный диапазон от 0 до 4294,967,295 (4 миллиарда) или, иначе говоря, в 8 раз больше пользователей, чем в настоящее время. facebook или половина всего населения планеты.
если вы думаете, что ваше приложение будет работать с такой скоростью, вы можете использовать bigint unsigned, который достаточно велик, чтобы хранить количество секунд, прошедших с начала времени (большой взрыв)