MySQL GROUP BY/ORDER BY problema

Eso no es realmente cierto. Devolverá una fila aleatoria. En la práctica, esta suele ser la primera fila en el orden de la clave principal, pero no hay garantía. Las bases de datos que no sean MySQL no permiten esta práctica y generarán un error.

De todos modos, una forma de recuperar la ID más alta de mensajes no leídos es unir la tabla de mensajes dos veces. La segunda combinación solo busca mensajes no leídos. Por ejemplo:

SELECT  max(msg.ID) as MaxID
,       messages.from
,       max(unread.ID) as MaxUnreadID
,       users.userName
FROM    users
join    messages msg
on      users.ID = msg.from
        and messages.to = ?
left join    
        messages unread
on      users.ID = unread.from
        and messages.to = ?
        and unread.read = 0
GROUP BY
        users.ID
,       users.userName