I actually typed up and submitted a lengthy and well thought out reply to this days ago and (even received kudos points for it so know it went through) and now it's no longer here. That's very odd.
Fortunately, I have a clipboard backup of that text:
Rebooting will temporarily correct the problem, however it returns within a short time. I'm actually experiencing this behavior across multiple different PC installs and uninstall/reinstall does not correct. I actually added my version of Spotify to the OP, but it's 1.0.87.491.ge2a121fc and Windows 10 x64 build 1803 (all PC installs match versions).
After a little experimentation, I discovered that the correct behavior will return if I start playblack on a different playlist. If I had to guess at this point, I'd say it's likely a defect in the Spotify player related to syncing clients that manifests when a different device has the same playlist loaded as it's "now playing" (even if it hasn't actually played anything).
For now, I guess I will switch playlists momentarily and then return to the desired playlist. However, this workaround is a little disruptive (especially if performed interrupting party/gathering music) and often results in recently played tracks playing again, even in shuffle mode. I would encourage Spotify to look into whether they can repeat this synchronization problem and, hopefully, issue a fix.
I am moving around a lot and one of the things I really like about Spotify and distinguishes it from competing services is how (relatively) seamless it is to have multiple devices connected that sync playback. I will often initiate playback on a smartphone, monitor and curate the playlist on a laptop, and then hand off playback to another desktop, receiver, or wi-fi speaker. This works reasonably well, but seems to have some implementation flaws/limitations that may have been exacerbated by recent changes.