I noticed that even when you have pressed the "shuffle" button in Windows Media Player, it still always starts with the first song in your list. In other words, Windows Media Player only starts shuffling the songs after the first song is played.
This is extremely annoying, for you don't always want to start with one particular song, especially if that song isn't one of your favourites.
So to solve this problem, I simply created a one-second media file, and made it the first item in my list. This way, this file would always be played first, and then one second later I would have a completed shuffled list.
If anyone wants to try this method, and doesn't know how to create an empty file, you can download one here.