Unfortunately useful things usually require much more computation to find a useful result, they require distributing the search, and so can't reliably verify th

Unfortunately useful things usually require much more computation to find a useful result, they require distributing the search, and so can't reliably verify that you performed the work (most searches will not find anything, and you can just pretend to not have found anything without doing any work). If a service had enough concurrent clients to reliably hit useful results quickly, you could verify that most did the work by checking if a hit was found, and either let everyone in or block everyone according to that; but then you're relying on the large majority being honest for your service to work at all, and some dishonest clients would still slip through.