Someone correct me if I'm wrong, but wouldn't another way around it be to split up the collection into smaller playlists, and play just those playlists?

i.e., I'm assuming he only runs into the problem when trying to shuffle the entire music collection.