The computational task can get arbitrarily larger, if the recipient system doesn't like the look of the mail. I can picture the MDA going, "wow, I decrypted this one, but it scores 9.2 on my procmail filter scale, so I better ask for and get fifteen MIPS-minutes of CPU time before I actually deliver it."
Stuff like this can be done anonymously, can be done on the recipient and sender machines, can depend on filters (the MDA sees it after it arrives and gets decrypted) and limits the per-machine rate at which a spammer can send spam.
This doesn't fit Joe Lunchbox's current model in which he dumps his outgoing mail onto his provider's server and turns off his machine. His provider either has to deliver synchronously and bounce the computational payment burden back to Joe, pay it for him, or bounce the message. In the latter case, the receiver who demanded cycles needs to recognize the problem it set and accept the answer on a later date. Matt Crawford