I had a few issues with Spotify doing this. I even saw a post where an engineer claimed it was all psychological, but I was definitely getting repeats when I had queued up a large amount of music (e.g. over 40 hours.) I think they only shuffle a certain percentage of the playlist and forget which songs have already been played after a while.
I manually shuffle some playlists now. One nice thing about the desktop client is the clipboard integration. You can press cmd+a to highlight all the songs, cmd+c to copy, and then paste all the song URLs into a text editor. Then I used "permute lines" in Sublime Text to shuffle them, then cmd+c and cmd+v to paste the songs back into Spotify.