Shuffle only plays recently added tracks

[badrul]

When shuffling all "Songs" saved to my library, Spotify only plays the most recently added ~100 or so tracks. This is an ongoing issue (searching keywords returns threads going back as far as 2013).

Please don't suggest workarounds such as "add all your songs to a playlist, then shuffle" — let's work on a long-term fix or provide an explanation if this is an intentional setting, thanks in advance.

Plan: Premium

Country: USA 

Device: All devices (iOS, desktop, web player)

Operating System: OSX 10.14.1

[stoli_man]

Also an issue on Android. Playlist doesn't work as a workaround - I'm experiencing the issue with the playlist. 

On FAQ it says if using Spotify Connect it will only shuffle 100 most recent songs. This is ridiculous. This confirms I'm not going crazy (kept playing the same songs...) but doesn't offer a solution.

I pay for premium and so I can stream to my speakers, shuffle, etc.

How is this still an issue?