Dieguicho,
a ver si hay suerte con esto. Yo no lo he probado:
Código sql:
Ver originalSELECT me.id, me.id_usuario_envia, me.id_usuario_recibe FROM mensajes me INNER JOIN
(SELECT m.id_usuario_envia USUARIO, MAX(m.id) ULTIMO FROM mensajes m
GROUP BY m.id_usuario_envia)t1 ON me.id = t1.ULTIMO AND t1.USUARIO = me.id_usuario_envia
Luego te tocará cruzar este resultado con la tabla usuarios para averiguar los nombres de ambos usuarios.