Interesting idea is rate limiting the client by requiring him to solve a puzzle for his request to be handled.
If his last request was recent make the puzzle harder. If last request was less recent make puzzle easier.
The puzzle might be like the one in bitcoin mining protocol. Guessing which bit string with specific amount of zeros at the end produces some random hash.
That would help against Sybil attacks, since a rate limit on a free service could be avoided by making more accounts. It does have the issue of being dependent on the client’s hardware to provide a server-side rate limit, though.
If his last request was recent make the puzzle harder. If last request was less recent make puzzle easier.
The puzzle might be like the one in bitcoin mining protocol. Guessing which bit string with specific amount of zeros at the end produces some random hash.