I actually want to see it on kind 0 (or at least, it should only be over the pubkey + nonce, it could still be attached to kind 1s though).

On kind 1s, a spammer and a legitimate user are on completely equal footing, whereas on kind 0, the spammer needs to regenerate a new POW for every new account (once it gets blocked) and a legitimate user only needs to generate it once, which means the legitimate user can invest more into their single proof.