As it pertains to this new series, I was reading here and there that some folks found their iTunes random setting wasn’t really all that random. It seems that the algorith does randomize your collection, but then holds that new randomized list in place. It does this, mainly, so that you can easily skip back to a previous song, rather than having to go searching for it again.
The simple fix is simply to toggle the random play off and then on again whenever you want it to freshly randomize your collection. This creates a new randomized list.