The best thing would be to download the free trial and try it out. You can use MC for a full 30 days without registering it (no restrictions).
However... I don't think you'll have that problem.
One important point, however, is that you'll want to do the shuffling on "the Lists" (the Smartlists or Views) that you play. There is also a shuffle button on the UI, which does this to
any list (or view) that you play automatically when you play it. However, and this is where MC differs a bit from other players, once files get added to the Playing Now list, that is
the precise track list and order they will play. You can rearrange the Playing Now list manually, if you want, but it does not continue to "shuffle" as you go, even if you have the Shuffle-Mode button enabled. That button just makes it so every "view" or "playlist" that you play, will be sent to Playing Now in a shuffled state. Yes, though, to answer your question, their random seeding works "right" and won't generate identical results each time (I don't know how cryptographically "correct" their random seed source is, though I know they just tweaked it in a recent build for some esoteric reason, in any case, it is sufficiently complex to confuse a human listener).
Now, of course, you can force Playing Now to reshuffle if you want (even just "reshuffle remaining tracks" to exclude anything already played), but... I just wanted to make that distinction clear. If you play the same Playing Now list (just open MC and hit "play" without picking anything to play), it will continue from where it left off and play the same list each time.
That said...
MC has lots of powerful "shuffle" capabilities. Check out this thread I contributed to a while back where I explain one of my (many) "auto-shuffling" schemes:
http://yabb.jriver.com/interact/index.php?topic=77395.msg524805#msg524805Also, MC includes a feature called Play Doctor (which I use to extreme ends in that example) that is something-like iTunes Genius (though it actually predates that Apple feature by a bit)... It uses an internal algorithm to decide what to play based on play history (play counts and skips), ratings, Date Imported, Genre, and all sorts of other metadata. The cool thing is that it doesn't decide what to Play "Next" until the current track is complete/mostly-complete. So, it gets smarter as you use it for a particular play session (usually, if you don't confuse its computer-brain). As you skip past tracks that it chose badly, it "crosses them out" and considers that feedback more heavily for this Play Doctor Session.
It is pretty cool. You should check it out as you play around.
In any case, with the various "shuffling" and filtering schemes you can apply to both Views and Smartlists in Media Center, including:
~shuffle
~mix
Play Doctor
Not to mention extensive Automation options (including reshuffling Playing Now from the command line, if you need it)...
I don't think you'll be left lacking in your desire.