I was under the impression that the re-shuffled playlist order isn't necessarily the same, it just puts the tracks that haven't played yet after the current one and the tracks that have played before the current one.

But I don't have a player handy to test.