Those third party search tools already exist. I expect that apps will begin linking to them or even including their own version of the same function.
And really, it's vanishingly unlikely that somebody so dull-witted that they couldn't even find the most notable instance on a given topic if it wasn't already on their instance's All is going to end up on such an obscure instance in the first place.
Again, I don't think it's a usability problem at all - I think it's just people expecting the fediverse to be essentially identical to the monolithic corporate social media to which they're accustomed, then faulting it for not being so.