Maybe each request should be accompanied by a proof-of-work, proving that the requester invested at least 10s of computation...