How much work would you propose is sufficient that grandma doesn't mind but spammers will be severely hampered in their sending and in a manner that doesn't require the receiver to store too much state?
Only a small amount is necessary. There is a protocol called hashcash (used by Bitcoin but generally applicable) that can be easily used with email [1]. You basically get a header like this:
You can choose how much work you want to do and the recepient can specify thresholds for minimum work required. This header is all they have to store, and it's easily stored through existing email infrastructure. Your mail server can do it without your client's help, too. If you spent a second on a proof I'm sure grandma wouldn't notice, but it would be very difficult for spammers to do the same.
For one, it'll only work if both sender and receiver use it. Which means for 99.99% of mail traffic right now, it is utterly meaningless.
edit: Plus you also literally wasted everyone's time and energy.
I'd rather favor some kind of mechanism like grey-lists that don't require sender opt-in otherwise it'll be a dead technology just like GPG. (You can probably count the number of GPG emails within 1000 average mails on one hand)
We make incremental change. Adoption starts slow, then some middle players pick it up, one big player grabs it and then it proliferates. I've been working on a mail client for some time and I have plans to write a mail server, and both will have first class, opt-out support for hashcash.
