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.
What are the odds of this happening?
You wouldn't listen to a playlist of 10 songs when there are many of them in it you are not in the mood for?
Just about every album I have has one song that I will routinely skip over, because I don't like it much.
Or rate it poorly and factor ratings into your smart playlist.
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.
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.
I'm not seeing how any of the suggested changes are an improvement.
Yes, the current scheme isn't mathematically random. That's irrelevant unless mathematically random is a better user experience.
So, let's see some evidence for different schemes that improve the user experience. Note - users don't care about mathematical purity.