I sure hope this was a mistake on Spotify's end.
After a search, if I click on anything the search disapears and the list of songs and order goes back to what it would have been before the search. The "cancel search" animation is shown.
For example, lets say I want to listen to Linkin Park. I search "Linkin Park" in my "starred" playlist, because that is much easier than creating a new playlist.
As long as I just click play and don't touch it from here on, it is fine.
However, if I want to do anything else, such as clicking on the song banner on the bottom to access shuffle/repeat controls, adding one of the songs to a playlist, etc, I see a weird little animation (the cancel anmation), and the search disapears, causing the next song played to most likely not be linkin park.