I have the same big when playing a large playlist on my Google audiocast from my android phone. I have a playlist of about 3000 songs. When I start the playlist and shuffle, only the top 100 songs are used by Spotify.
When I shuffle in Spotify when my phone is not connected to the audiocast, it will shuffle correctly. Connecting again to the audiocast it will limit the shuffle to 100 songs again, but now from the selected song (e.g. songs 2000 to 2100 are shuffled now)
I'm having this issue as well when using Alexa and/or a wireless connection to a speaker. Only the first 100 songs or so get loaded into the queue. I never hear the other 2,900 songs in my master playlist. Pretty frustrating.
This issue is still not fixed, as it happens when I play on Spotify Connect (NAD BluOS) from my iPhone or MacBook. Just to test it, the same issue occurs when playing from iPhone on MacBook and vice versa. So it seems like Spotify is limited to use only the first 100 lines from any playlist. I was in contact with NAD Bluesound support, who could tell me the playlist isn't transferred, but is still handled locally by the mobile/computer when playing on a remote device.