Steps to reproduce:
1. Load a playlist of N files in VLC
2. Set playback to Random
3. Play or jump (with ”Next” button) the playlist forward for N files and observe the playing order
4. GOTO step 3
The order in which the files are played in step 3 always repeats itself.
What I expect to happen:
For the files to be played back in a truly random order, without any perpetually repeating pattern.
The playing order seems to get shuffled only at the start, so the playlist isn’t played in order, but the once-shuffled order is repeated over and over. To reshuffle the playlist, VLC has to be restarted, but still then it just plays the newly-shuffled playlist over and over.
To be fair, in practice instead of true randomness I suspect most people prefer something from the way the ”Random” now works: that each file on the playlist is played once and once only in every N plays. AFAICT it is not mutually exclusive with reshuffling the playlist between those N plays; just make sure that the two transitional files (last file of shuffled-playlist-1 vs. first file of shuffled-playlist-2) aren’t the same.
I for one though would still prefer even true random over what it currently is.
Of the half a dozen or so randomness-related bugs in VLC’s tracker I was able to find, Ticket #5730 (”New Feature Request: Shuffle & Random for Playlists”)  came closest to what I’m reporting here. In fact, it’s a superset of this one and I’d prefer to have it fixed over just mine.