Orden aleatorio consistente en una consulta MySQL

Puedes intentar usar semilla en una función aleatoria:

SELECT something FROM somewhere ORDER BY rand(123)

123 es una semilla. Random debería devolver los mismos valores.