True randomness has a lot more "clumping" than seems intuitive.

Hmm, if the songs never show up, it might be worth checking, whether they can be played when you select them manually. I've had it before where the particular music player didn't understand the file format or the metadata of a song, so it just silently skipped it.

But yeah, otherwise that's weird. Obviously, some of the more corporate music players will try to do weird stuff with how shuffle works, but there's so many open-source music players out there, where I just don't see why they'd bother to implement something else than randomized order...