Таблица такая: Messages(id, user_from_id, user_to_id, text, msg_time, ...).
Никаких предыдущих номеров Вам запоминать не нужно и никаких записей с одинаковым номером не будет. В таблице Messages поле id делаете
автоинкрементным и забываете обо всем, что вас беспокоит.
Как получать историю:
select *
from Messages
where
user_from_id = $id_пользователя or
user_to_id = $id_пользователя
order by id