Essaye ça. Déplacer la sous-requête vers le JOIN semble résoudre le problème. Je pense que le problème a à voir avec la sous-requête dans la clause WHERE. Je pense que dans la clause WHERE, la sous-requête et la fonction RAND sont exécutées pour chaque enregistrement. C'est probablement la raison pour laquelle les résultats varient.
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