Для СУБД поддерживающих оконные функции, т.е. MS SQL, Oracle, Postgress:
select * from (
select M.*,
row_number() over(
partition by case sender when MY_USER_ID then recipient else sender end
order by date desc
) N
from mailTable M
where MY_USER_ID in(sender,recipient)
) A where N=1
Для MySQL:
select * from (
select M.*,
@n:=if(@lid=if(sender=MY_USER_ID,recipient,sender),@n+1,1) N,
@lid:=if(sender=MY_USER_ID,recipient,sender)
from mailTable M,(select @lid:=NULL,@n:=0) A
where MY_USER_ID in(sender,recipient)
order by if(sender=MY_USER_ID,recipient,sender),date desc
) A where N=1
Общий вариант, скорее всего более медленный (работоспособность не тестировал):
select * from mailTable M
where (sender=MY_USER_ID or recipient=MY_USER_ID)
and not exists(
select 1 from mailTable X
where ( (X.sender=M.sender and X.recipient=M.recipient)
or (X.sender=M.recipient and X.recipient=M.sender) )
and X.date > M.date
)