In the states, large streamers like SoundCloud are now required to identify and pay royalties for covers. (Streaming rates were still TBD when I checked probably a year ago - the wheels turn slowly.) So, in general, you no longer have to purchase "mechanical rights" for your streams on a site like that. (You do still need to purchase rights for a CD, and there are a lot of services that can do that.)
It's fair to say that while you *should* have been purchasing rights for streams of covers on SoundCloud, the overwhelming majority of folks never did that, which is why the laws are changing.
The only choice you really have is to do what you have already tried, i.e., see if a song cover has already been posted a lot. If it has, it's probably Ok. If it has not, and it's not something obscure, then you might want to do the kind of checking
@rob aylestone suggests.
BUT, in general, you cannot determine if a specific copyright holder has not agreed to allow their IP to be used in that fashion. YouTube is the best example of one that's been negotiating and paying for the covers published there, where probably something like 98% were done without obtaining the rights. When you do that you see a "Copyright Claim" notice in your YouTube page. You didn't pay anything, but YT's scanning/checking/AI stuff identified it and as a result some publisher/copyright owner is getting their $.02 for every 10,000 plays or whatever the rate is. It adds up, I guess. The one catch is that not every copyright holder has agreed to this, i.e., YT doesn't have a negotiated stream payment rate deal with them, and if you publish a cover without specifically obtaining the rights (which they likely will not sell or grant), then YouTube receives a "take down" letter and you get a "copyright strike". They just recently started a process where they will pre-scan your video before publishing, and not publish it, possibly saving you the strike (3 strikes and your channel is shut down), HOWEVER, they cannot predict that your particular cover still won't cause a letter to be generated, e.g., if you do some horrible parody that somehow offends someone, or maybe they just changed their mind, or the copyright was transferred and the new owner has different plans. I have not heard that SoundCloud ever did the "strike" thing, but no doubt they have removed some covers, though I never had a problem.