How reliable is the song matching on YT? I’d imagine some songs would be obscure or exclusive to Spotify so that you can’t find it on YT, let alone it being a low quality one.

I’d approach this problem by using Spotify’s API (or scraping) to get the good stuff, then sending it to my phone whenever I’m connected to the wifi.