you are right about the “same 5000”, but this was already fixed in this release:
We never let you add more than a few thousand tracks to the queue, but having the ability to shuffle in more than 5000 tracks is an important use case, so we added this wacky shuffle “mode”, which was different than radio, and different to queue shuffle. It created a lot of confusion.
So, to solve this confusion, we decided to eliminate the confusing “shuffle mode” and just add tracks to the queue w/ shuffle on.
The problem is if you hit shuffle or play or something in more than a few thousand tracks, it’ll overload your queue. The solution was to do the shuffle algorithm up front and add the first 5000 tracks added to the queue, which should be about 4-6 days of music.
In the first 1.8 release, we had a bug where it truncated the list to 5000 and then shuffled. That gives you the buggy behavior you see, but it was fixed in the above release.