En realidad no usa random (eso sería si la cláusula dijese ORDER BY RAND(), y no es el caso).
El problema es que la sintaxis de MySQL exige que el GROUP BY vaya antes del ORDER BY, por lo que los registros repetidos quedan "escondidos" detrás del primero que está en la tabla.
La solución es simplemente poner el resultado del ORDER BY primero, pero en una subconsulta:
Tip: El ORDER BY es siempre ASC, por lo que solamente debes indicar algo distinto si quieres otra cosa.