Consulta MySQL con condición de subconsulta RAND()

Prueba esto. Mover la subconsulta a JOIN parece solucionar el problema. Creo que el problema tiene que ver con tener la subconsulta en la cláusula WHERE. Creo que en la cláusula WHERE, la subconsulta y la función RAND se ejecutan para cada registro. Esta es probablemente la razón por la que los resultados varían.

SELECT  a.AlbumID,
        Videos_Demo.VideoID,
        VideosInAlbums_Demo.AlbumID

FROM    VideosInAlbums_Demo

        LEFT JOIN Videos_Demo
        ON Videos_Demo.VideoID = VideosInAlbums_Demo.VideoID

        JOIN 
        (
            SELECT  AlbumID
            FROM    VideosInAlbums_Demo
            WHERE   VideoID = '1'
            ORDER BY RAND()
            LIMIT 1
        ) AS a ON VideosInAlbums_Demo.AlbumID = a.AlbumID