Hola :)
Te cuento :
Yo he tenido ese problema y hay varias formas de resolverlo, una sencilla y otro compleja :
Sencilla -> Llamar a todas las imágenes con un número, y luego hacer un random:
Código PHP:
$imagen = rand(1,40);
Print ("<a href='videos/videos.php'><img src='../aleatorias/$imagen.jpg' width='120' height='100' border='0'></a>");
Compleja - > Listar todo s los fichero y elejir por random uno, con lo cual solo con que subas el fichero al servidor se mostraría. Esto tiene el problema del tiempò, que tarda mucho. y para que no pase eso, puedes grabar en un fichero de texto el listado y una vez a la semana comproar si hay nuevos ficheros en la carpeta.
dime si te vale :)
saludos