Hola,
Es el eterno problema con los numeros aleatorios en informatica. Nunca son lo suficientemente aleatorios.
El mayor problema que he encontrado yo es que el primero se repite mucho, el resto varia mas.
Una opcion seria hacer la consulta de todos los registros con el order by RAND(), meterlos en un array, hacer el shuffle del array y usar la funcion
rand() de PHP (con su correspondiente srand()) para generar el indice del array. Asi metes tres niveles de aletoriedad: MySQL, shuffle y rand.
Suerte, y ya contaras.