Tente isso. Mover a subconsulta para o JOIN parece corrigir o problema. Acho que o problema tem a ver com ter a subconsulta na cláusula WHERE. Eu acho que na cláusula WHERE, a subconsulta e a função RAND estão sendo executadas para cada registro. É provavelmente por isso que os resultados estão variando.
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