I don't typically run into missing stuff, but I usually find music through their UI instead of searching for particular tracks.

I think they advertise a larger catalog than Spotify, but that could be padded with tracks nobody cares about.