I noticed there are a lot of posts on this subject, and I don't want to come off as just another complainer.. but this situation I think might be a little different..
I have a playlist of 900+ songs that I regularly use. the first time I used it with shuffle was fine and I listened for about 25 songs, but as time went on, I noticed that those same 20-25 songs that came up that first time were coming up every time I started up that playlist on shuffle again, randomly still, but always within about the first 40 songs at least 20 from that first listen would come up again. even if I reshuffled in the middle of a song a lot of them would still get queued up at the beginning of the list. it's now gotten to the point where it gets very annoying to hear those same songs and have to skip that many of them every time I open that playlist when there are 850 more that never get played. it seems like what's happening is that every time a song gets played, that increases the chances of it being played again next time you use that playlist on shuffle, which probably isn't even possible, but I swear that's what it looks like is happening.
I guess my (stupid) question would be, is there a way to make it "more" random than it already is? some parameter that can be tweaked or something?