I probably have some details wrong, but according to Spotify's customer feedback site, there at least used to be a couple of issues with their shuffle. One, if

I probably have some details wrong, but according to Spotify's customer feedback site, there at least used to be a couple of issues with their shuffle. One, if I remember somewhat correctly, was that if the player was stopped/shutdown, it forgot the shuffle seed. This would essentially lead to a reshuffle, which would cause duplicate songs for songs played before the unintended reseeding.