Mostrar los últimos mensajes de la tabla de mensajes, agrupar por usuario

Esto debería ser bastante eficiente:

SELECT u.name, sub.*
FROM  (
   SELECT DISTINCT ON (1)
          m.message_from AS user_id
        , m.message AS last_message
   FROM   users    u
   JOIN   messages m ON m.message_to = u.id
   WHERE  u.name = 'Paul'   -- must be unique
   ORDER  BY 1, m.id DESC
   ) sub
JOIN  users u ON sub.user_id = u.id;

Calcule todos los usuarios con el último mensaje en la subconsulta sub usando DISTINCT ON . Luego únase a los users de la tabla una segunda vez para resolver el nombre.

Detalles para DISTINCT ON :
¿Seleccionar la primera fila en cada grupo GROUP BY?

Aparte:Usar "id" y "nombre" como nombres de columna no es una convención de nomenclatura muy útil.