The trick is to start the compilation when you start showing the comment box -- and only show the "reply" button once it's done. This way, for nearly all comments, it will be done calculating before you are done commenting (this has already taken me more than 20 seconds!), and it retains its hard-to-spam properties.
My comment box is always visible, but I don't start the computation until the user actually focuses one of the fields. The submit button is disabled until the hashcash computation completes, but that's about it. If you're not racing the hashcash computation, you'll likely not notice anything unusual.
If you're writing off-the-cuff comments that take you less than 20 seconds to write, I don't want you posting them, so it's win-win.
I don't care if you prevent me from posting for 20 seconds, but if you make my laptop fan spin up, or cause my old computer to get unresponsive, especially if I have no clue why, I'm gonna be upset. I'm used to video sites slowing down the computer slightly, but if a simple blog does it, I'm gonna be confused, and possibly pissed.
I doubt that 100% CPU use for 20 seconds is going to make either of those things happen. Maybe reserve your anger for things that occur.