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 originalSELECT 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.