idea: pay for PoW over nostr:

Send note to a paid pow relay where you register your pubkey. The contents of this is a json-encoded unsigned note that you want PoW on.

Service decodes this note, does PoW, sends it back to relays encrypted. Client sees this, decrypts, checks it against the original note sent (that is encoded in the response for convenience), signs it, and broadcasts.