The problem, as stated by, literally, 100+ premium users on this forum is that the songs have been downloaded and saved on the phone, but one fine day, the phone won't read those downloaded files. It appears as though the songs haven't been downloaded anymore, despite the preposterous fact that they still take up phone storage. Not only does this problem recur multiple time, it happens seemingly sporadically.
It's been present for months, and I'm sure enough of us have waited patiently for any progress, be it what to do to avoid the situation, however ridiculous, or dare I say, an actual fix.
As a response to this : Link to bug
My entire library went, save a few songs (not the same ones), most times.
You're the largest music streaming company. Try and keep it that way, and respect your customers cause I know Apple does.