Verwenden Sie einen cte
und weisen Sie Zeilennummern zu, sodass alle bis auf eine für doppelte Paare gelöscht werden können.
with rownums as
(select m.*,
row_number() over(partition by ToUserId, FromUserId order by ToUserId, FromUserId) as rnum
from Message m)
delete r
from rownums r
where rnum > 1
