The top answer is good, but it doesn't explain why iTunes couldn't maintain the seed while skipping forward and back, but reshuffle whenever a new song is selected, or whenever iTunes is restarted, or whenever you switch to a playlist and back, or all the other times you wouldn't expect it to maintain the sort order. So this still seems like something that Apple could (and should) really improve on without breaking important functionality.
That approach could have some random unintended consequences. I shuffle my playlist and listen to a few tracks. One comes on that I don't like or doesn't match my mood, so I peek at the playlist to find on that does match my mood and double click it to start it playing. Unbeknownst to me, iTunes triggers a reshuffle when I do that, and the very next track to play is the one I was trying to get away from.
The better solution (at least from my perspective) is to not pretend that shuffle is a setting, but an action. Simply have a button that says something like "Shuffle this Playlist" or more explicitly "Re-Shuffle this Playlist". Play, stop, forward, back all would work normally within the existing order (straight or shuffled), and if you wanted a new order, you click the "Re-Shuffle" button.
In all those "why doesn't it reshuffle" scenarios you mention, I would then have to hear same tracks again. I don't want to. I want to hear everything, some today, some tomorrow, some next week, until I've heard it all.
Unless I do want to hear things again, in which case I toggle the Shuffle button.
By design, I decide. Rebooting, restarting iTunes, picking a particular song then going back to my long playlist, those don't decide for me.
Ideally, what I'd want is a button that generates a new, temporary, randomly-reordered playlist from another playlist, representing it as a virtual child (if I had, say, a "Vacation music" playlist, it would have a child node "Vacation music shuffled with seed 6e43bf".) The virtual playlist would also represent differently the songs that have been listened to since the playlist was created, from the ones that haven't--say, by putting a strike-through through them and greying them out slightly, or something. That way, if I get a whim to listen to one particular song half-way through listening to the shuffle-list, I can go listen to it, then return to the shuffle-list and listen to the rest of it, without having to hear any of the same songs again. This would also allow for the child to track modifications of the parent--if you remove a song from the parent playlist, it would also disappear from the child (unless, perhaps, you had already listened to it; then the child could keep it as a record); and if you add a song to the parent playlist, it would get inserted at a random position within the still-as-yet-unlistened partition of the child.
This is sort of what iTunes DJ will do, if work off a smart playlist based on the playlist you want to listen to, but which defines some criterion by which songs you've listened to won't come up again--for example, if you're listening to songs to give them ratings, you can define the smart playlist to only be the unrated songs in the original playlist; then each song will be removed from shuffle-selection once you've rated it.
Still, the simplest thing to do is to just set a playlist to shuffle, make sure the list view is sorted by playlist-order (the unlabeled leftmost column), and then Ctrl+A, Ctrl+Shift+N to copy the shuffled list into a new playlist, and delete songs from it as you listen to them. It's too bad this is an impossible proposition on a portable device.
Pressing Back to get to the song you just played, and double-clicking that exact same song, must absolutely behave identically or it will really confuse people.
I don't know what mathematical purity has to do with anything, I was just thinking Principle of Least Surprise, which is a user experience plus. Of course, I'm just going by what I would find least surprising and most useful, but I've heard lots of people express confusion about the behavior described in the StackOverflow question, so it does seem like there's room for improvement here.
