I've used spotify (premium) for a year or two with no problems, but I noticed yesterday that I can no longer listen to any track I've previously never listened to. If I recognize that I've listened to a certain track on spotify previously, or it is included in one of my playlist the track will play fine. If not however, the track won't play at all and I get the message "This track is not available. If you have the file on your computer you can import it."
No they're not saved for offline mode. I tried it on my Samsung S6 and I have no problem there. If I listen to a track I normally wouldn't be able to listen to on my phone, I can listen to it on my PC afterwards.