Switch to Spotify? Nahh. £12 a month for Youtube Music and Youtube Premium is a bit too good to pass up, even if YTM's interface is a bit cack sometimes.
I noticed gaps in the catalogue too, but usually the song was there in some other way, like a youtube video, so you could at least listen to it. It was annoying at first, but they have gone back and filled a number of those gaps (I haven't checked everything I saw was missing when I first started using it, but the ones I did check have been filled).
My only gripe with YTM is that it pulls from your Youtube history as well s YTM when making your offline mixtape. So now I have Seagulls (Stop it now), Dumb Ways To Die, and The Periodic Table Song along with my usual mix of Retrowave and Indie Rock.
(I'm too lazy to make my own playlists.)