Out of curiosity, does it happen on some clients and not others?

I remember hearing of a bug where if you played on a remote device, it would transfer the first part of your playlist (10? 100 tracks?), and then shuffle would only choose from among them.

But it's been 5+ years so things may have changed and/or I could be remembering completely wrong.