Shuffle doesn't (currently) work like CD players: basically, when you pick a playlist with the shuffle flag turned on, the playlist is built, shuffled, and saved - so it persists across boots and you won't hear the same stuff twice.
However, this also means that turning shuffle off during play has no affect whatsoever - it only affects the order the playlist is built in when you select a new one.
We're looking at the options on this, and it may change. We will ensure that it does behave sensibly across boots though.
Hugo