It happen to me often recently as well - I have same Spotify version 18.104.22.1682.gbd112320 For me it is connected with connecting to VPN (Cisco AnyConnect) Restarting resolve deamon helps: service systemd-resolved restart
Same here for version 22.214.171.1242.gbd112320 on Linux Mint 19.1 . The issue occurs seemingly randomly, sometimes resolving itself after a few minutes, sometimes not. Similarly, messing around with the network connection (re-connecting to WiFi, connecting/disconnecting to VPN) sometimes fixes it, sometimes not.
That's interesting. I've had this issue on only elementaryOS(18.04), Ubuntu 20.04 and 20.10 (and several other editions like KDE Neon).
But I'm currently running openSUSE Tumbleweed with the spotify-easyrpm package (spotify v. 126.96.36.1992.gbd112320, it's essentially just the .deb file converted to RPM and then installed) with no issues both with my ISP DNS and Cloudflare's DNS.
I begrudgingly installed the desktop app after getting sick of all the limitations of the web client (which I'd much rather be using if it wasn't so stripped down), and this has been a constant problem for me as well. It sometimes happens at random, but also happens 100% of the time when I hibernate my computer. The only fix is closing and re-launching the application. Whenever Spotify decides it's offline, it's still able to stream songs (because I'm not offline), and Spotify Connect still does its whole thing (because I'm not offline), but I'm artificially locked out of most other functionality. Wireshark confirms that songs are actually being streamed over the internet, not from a local cache, and also shows that the client doesn't make any other attempts to load requested pages when it thinks it's offline, even though it would succeed if it bothered to try.
A simple "check again" button in the "no internet connection detected" message would be a viable workaround for me.