(не проверено ...;)
CREATE PROCEDURE GetConversation
(
@user1 BIGINT
,@user2 BIGINT
)
AS
Select [FromUserID], Date, Text from Messages WHERE [FromUserID] in (@user1,@user2) AND [ToUserID] in (@user1,@user2) ORDER BY Date DESC
Обратите внимание, таблица 'Users' необходима только в том случае, если вы хотите отобразить конкретные данные пользователей.Например: отображение имен пользователей вместо их идентификатора.Вы будете архивировать это с помощью простого JOIN.
@ Редактировать: в начале вопроса не было «хранимой процедуры» в заголовке вопроса.