Yeah, PoW can be built into the binary version of the npub (no nonce), or into a hash of any values. To prove we aren’t just reusing an old PoW i guess it should be a hash of the contents of the signed message. The PoW verification would work nicely into the signature verification flow.