Это не работает, потому что mysql может вернуть любую строку из группы, независимо от того, как вы пытаетесь упорядочить свой набор. Чтобы найти первую строку в группе, используя некоторый пользовательский порядок, вам нужно разделить ее на две задачи - сначала найти все отдельные значения для столбца, по которому вы группируете, а затем найти первую строку в подзапросе для каждого ссылочного значения. Поэтому ваш запрос должен выглядеть так:
SELECT toD.username AS ToUser, fromD.username as FromUser, msg.* FROM
( SELECT DISTINCT touserid, subkey
FROM usermessages
WHERE touserid = 'insert_your_id_here'
AND deleted=0 ) msgg
JOIN usermessages msg
ON msg.id = ( SELECT msgu.id
FROM usermessages msgu
WHERE msgu.touserid = msgg.touserid
AND msgu.subkey = msgg.subkey
AND deleted=0
ORDER BY msgu.read ASC, msgu.created DESC
LIMIT 1 )
JOIN users fromD ON msg.fromuserid = fromD.id
JOIN users toD ON msg.touserid = toD.id
Убедитесь, что у вас есть индекс (touserid, subkey). В зависимости от того, насколько велик ваш БД, вам может понадобиться больше.