[MayeulC]

A simple proof-of-work would use a hash function (sha or something like blake2, in javascript or webassembly, can be multiple rounds), plus a server-provided random seed. Append random data to the seed until the hash function matches a certain condition. Submit the data to the server for checking. Something like that pseudo-C code:

    for(i=0; i<INT_MAX; i++) {
      output = hash(concat(server_provided_data, i));
      if(check_output(output))
        break;

With check_output checkig that the leading n bits are all zero, for instance, with n the difficulty. On the server-side, no loop is needed: only one check with the server-provided data and client-provided "i" is enough. In practice, i is probably going to be much larger than 32 bits, and any cheap way of changing it shold be enough, it doesn't have to be linearly increasing. I imagine countless proof-of-work libraries exist.

The issue with that approach is that slower clients will take longer to solve the challenge, but it just needs to be prohibitely expensive (and slow) for the attacker to spam this, even if they have powerful machines. Botnets can sidestep the issue a bit by distributing computing, but this should still slow them down.

You could also ask for the client's best find after x seconds if it's low-powered, and check that it is reasonable (though that can be gamed). The difficulty can also be increased temporarily if there is a surge of requests.

Maybe we need some kind of "Internet weather forecast" to adjust captca difficulty across websites according to detected botnet activity?

[GoblinSlayer]

Your solution is for mass spam. For this Amazon abuse it may suffice to send 20 messages.

[MayeulC]

It's true, I assumed there would be multiple targets, maybe that was misguided?

You probably can't use a single website to send those 20 messages (if it's well-designed with a cool down), as the recipient address is the same. So you need 20 different websites to send these.

What outgoing spam rate is acceptable, assuming you can't reach zero? 1 per 10 sec?