There's an even simpler solution I've used ever since I became aware of the first amplification attacks during the 00s: either implement your own simple 3wh, or if you really want a simple request/reply protocol with no state associated, pad the request so it matches the reply in size. Sometimes your reply is large though and needs a couple dozen packets so then you're usually forced to use the first solution.

You’d have to keep track of which proofs you’ve already seen, to prevent re-use. You’d have to make sure the (source, source port, destination and destination port)-tuple is a cryptographic part of the algorithm, to prevent me using the same proof of work for like a million machines.

Then there’s the issue of low power and/or battery-powered devices. You want people to be able to use your protocol without draining the battery. But by lowering the computational cost to accomodate that, you’re enabling the bad guys that can afford a fast GPU to go back to abusing the protocol cause the cost isn’t sufficiently high to deter them anymore.

And I’m sure there are plenty of other things I haven’t thought of.

Yes, you can for example require the first datagram in a connection to have a cryptographically signed blob of data (also useful for key exchange). But then you need some mitigation against a simple replay attack (client sends same packet twice).

The server's first response should be much smaller in size than the client's request.

The basic idea is to make the client (attacker) use more bandwidth and CPU time than the server, at least during the connection handshake phase. This makes the server unappealing as a target for attack, even through it does not downright prevent the attack.

Most protocols already employ such schemes in connection handshake and crypto key exchange.

A three way handshake would be simpler and wouldn't waste cpu and energy.