Stateless proof-of-work system with 0-roundtrip time
Is the requirement to prevent replaying identical requests? If not, it seems trivial to use a partial inverse hash of the request body.

If you are concerned about replaying identical requests, one possibility might be to use the proof-of-work nonce for your load-balancing algorithm. For example, use the least significant 3 bits to distribute across 8 servers. The long run average should distribute fairly between workers but a replayed request will always end up going to the same worker. SO you can check for duplicates locally without needing access to a global state.