Я бы сделал так:
message_id int,
time datetime,
message_body varchar,
friend_id int,
flag_deleted bool,
flag_readed bool.
Ну, эт я в общем. Да ж не мускуль, а так.
Ну и когда обрабатываем на вывод из таблы, то забираем все с опущенным флагом flag_deleted
Типа вот так:
select * from messages_table where flag_deleted != 1;