Prova questo. Lo spostamento della sottoquery in JOIN sembra risolvere il problema. Penso che il problema abbia a che fare con l'avere la sottoquery nella clausola WHERE. Penso che nella clausola WHERE, la sottoquery e la funzione RAND vengano eseguite per ogni record. Questo è probabilmente il motivo per cui i risultati variano.
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