Can't they delete it from your device if so they wanted?
I've suffered the same, as content agreements have changed, tracks have been made unavailable in playlists.
There's a setting in Spotify to see this; you can disable "hide unplayable tracks in playlists". You'll then see all the affected songs return, but greyed out.