Interesting... I was not able to reproduce this on Spotify on my Android phone. That is not to say it is fixed because I have only spot checked. Some spotify comms on the issue would help.
I cannot say whether this is completely resolved or whether the max shuffle has been upped from 100 songs to a higher number (hopefully 4000+). I have also not tested this on other platforms such as my TV or audio receiver yet, as both have native spotify apps installed.
1. Open a playlist with more than 100 songs.
2. Click shuffle play.
3. Confirm song is not in top 100 of the playlist songs.
4. Press skip.
5. Repeat steps 3. and 4. until a sufficient sample of records past the first 100 has been observed.
250 tracks, whereof the name of 50 starts with A, 50 with B, 50 C, 50 D and 50 E.
Check that it's sorted by trackname, and start playing with the first song.
Check that Shuffle is turned on, and hit next a number of times.
You will easily see if all track names starts with A and B only.
Also, anywhere you start in the list, if it plays only the 99 closest tracks to the one you currently are playing, the 99 before or 99 after, it will never show more than three different starting letters.
No, I was wrong. The bug is also not solved for me. Somehow I got a shuffle from a long playlist from my laptop, through my phone, on my audiocast. But it was still a limitied playlist, and when I shuffled again I got the standard shuffle of 100 songs from the 3000+ playlist.
So it is not solved, sorry to give you new hope. It would be nice if this finnaly got fixed by spotify.