I like how my Onkyo changer does it. I doesn't scan the trays ahead of time. First it skips to a random tray. If it's empty it moves to another tray. When it finds a disc, it scans the index for the number of tracks, adds it to its disc/track index (so that it can keep track of the ones it has played), and then chooses a random one on that disc to play. When that track is done, it may play another on the disc or move on to the next random tray which may or may not contain a disc. It doesn't repeat tracks.
