He aquí un breve experimento para ver qué sucede.
create function determin_rand (i integer)
returns float DETERMINISTIC
return rand();
create function not_determin_rand (i integer)
returns float
return rand();
select determin_rand(1) as d1 , determin_rand(1) as d2,
not_determin_rand(1) as nd1, not_determin_rand(1) as nd2
0.00850549154 0.831901073456 0.133989050984 0.174242004752
Dado que los valores son diferentes, la función se llama cada vez. En la primera función la declaré determinista, pero no hizo ninguna diferencia.
Hice un sqlfiddle para que lo pruebes con diferentes versiones de mysql.
http://sqlfiddle.com/#!2/a8536/2