I have been dealing with this for about a year now. I listen on my motorcycle while out in the sticks often, and because service is so spotty, I keep a huge library local on my device. However I don't put it in offline mode since often enough I do have service.

Once I get that "No internet connection available" message, the amount of coaxing to get it to play locally saved music is insane. Usually it is some combo of app restarts, toggling "offline mode", and toggling airplane mode on my phone that will eventually get it to play.

Spotify. Please figure out the surely 5 lines of code that would fix this. I'm sure this bug even predates my finding of it.