I remember when the iPod first came out and was truly random. People would notice that song X came up twice before having played song Y and conclude that the iPod wasn't truly random. There was a big thing on Slashdot about how the record labels were paying off Apple to weight certain songs more heavily in the shuffle for their own nefarious purposes.

Then again, my memory isn't what it used to be, so maybe the Slashdot crowd was right about that one and I just forgot.