As with most Google Search features, it seems to have been degraded/nerfed over the years (as has competitor Shazam). I'm starting to think it's purposeful and on account of limited compute: devote a lot on launch to convince people of its quality, then gradually lower resources devoted to it. As long as 90% of searches - the ones for the most popular songs - work, the complaints from the subset of the 10% that don't won't rise to the level of requiring attention.
