Given that there's a form of PoW when registering for normal websites, be it in the form of complex captchas, doing so would be good.

I guess for existing pubkeys, they would need to submit a kind 0 update with a high PoW?