I have one....I don't use folders unless I'm making a CD of albums....but I haven't had any problems with the random feature, although I don't use it that much.
Try it and find out....
It MAY be related to me overriding the song it selects. for example, say I have 100 songs on the disk, and it picks song 50. I may change folders/tracks to listen to a different song, but it will come back to song 50 within the next 3-4 songs or so. Almost like it has to play that song completely before it can re-randomize.
"The world is full of people who want nothing short of perfect,
but settle for less, blinded by their quest for purpose."