Tons sería mejor almacenar la posición desordenada de los videos primero y luego irlos reproduciendo así:
Código ActionScript:
Ver originalvar varArrayVideos:Array=new Array("nombre_video1","nombre_video2","nombre_video3","nombre_video4","nombre_video5","nombre_video6","nombre_video7","nombre_video8");
var varNum:Number=0;
varArrayVideos.sort(function (){return Math.round(Math.random())});
player.url = "videos/"+varArrayVideos[varNum]+".flv";
varNum++;