php Mysql Agrupación y ordenación de mensajes de usuario juntos

Quieres:

Tendrás que hacer algo de magia en la cláusula group by para que esto suceda.

SELECT id, sender, receiver, MAX(time_sent), MAX(message) 
FROM Messages
WHERE sender='$userid' OR receiver = '$userid' 
Group By (if(sender > receiver,  sender, receiver))
       , (if(sender > receiver,  receiver, sender))
Order BY time_sent DESC