Если указанные вами определения таблиц полны, вы можете указать дату каждого сообщения, чтобы вы могли упорядочить их по дате.
Кроме того, это может быть несколько более эффективный способ выбора:
SELECT id, message
FROM messages
LEFT JOIN messages_read
ON messages_read.message_id = messages.id
AND messages_read.[user_id] = @user_id
WHERE
messages_read.message_id IS NULL