I second that I have exactly the same thing happen to me all the time on both 126.96.36.199 and 1.1.16.
Also I noticed that when I save a playlist and load it the first time all the songs for the playlist will be visable. When I close StreetDeck and reopen StreetDeck many of the songs in the playlist will be missing. If I clear the queue and reload the same playlist all the songs will now be visable.
I have been able to replicate this on my CarPC and on my laptop in development environment. The attached .mp3 is one of the many songs that will always disappear when StreetDeck is closed then reopened.
10 - Château Flight - Baccula.zip
The song is pretty sweet house song if you like that sort of thing