I may have listed cmus in error. From the man page, it appears that it shuffles the whole library and queues it. Maybe I've added music and just happened to hit the same songs in the new queue. Still should look over the shuffle algorithm. I think new song priority would be an interesting concept to explore.