I have a 2000 song playlist that I especially like. Recently it has stopped randomnizing on my Mac and was playing the same 50 or songs over and over. Frustration! But I think I have found the answer, at least for now. We'll see how long it lasts.
Shuffle should be random. It's not random at all. Some songs play multiple times, some never play. I noticed that rebooting the device or doing something similar "resets" the shufffling method and then different songs start to play often and the other ones rarely come up.