La consulta de gnzsoloyo es más eficiente, eso está claro, porque el group by se aplica a los registros cruzados previamente con INNER JOIN (se ha hecho uso de los índices), ya están ordenados y te traes los datos necesarios, por lo que es GROUP posterior es mucho más eficiente; por contra en el otro caso, el del MAX(), que propuse yo, se hace necesario comparar todos los registros y sólo puedes traerte dos datos, lo que obliga a otro cruce.
Aplaudo la solución 

Dieguicho, ahora sólo quedaría traerte el nombre de usuario de la persona que recibió el envío: eso te obliga a un autojoin dentro de la primera con algo así:   
Código sql:
Ver original- SELECT t1.id, t1.id_usuario_envia, t1.usuario, t1.id_usuario_recibe, t1.receptor FROM (SELECT mensajes.id, mensajes.id_usuario_envia, usuarios.usuario, id_usuario_recibe, usuarios2.usuario receptor, mensajes.mensaje 
- FROM mensajes 
- INNER JOIN (usuarios usuarios, usuarios usuarios2) ON usuarios.id = mensajes.id_usuario_envia AND usuarios2.id=mensajes.id_usuario_recibe 
- ORDER BY mensajes.id DESC 
- )T1 
- GROUP BY id_usuario_envia ORDER BY t1.id DESC 
Yo, al menos, todos los días aprendo algo con 
gnzsoloyo.
Dieguicho, una aclaración final: esto es sólo si quieres traerte los nombres del que envía y recibe; si no es necesario, déjalo como lo tenías, porque esto (el ir dos veces a la misma tabla) ralentizará la consulta.