Let the sender prove that he is indeed a human being and not a spamming machine by letting him recognize some distorted characters displayed as a png-image. This is hard for a machine to calculate and thus hinders automatic spamming. I think I already saw this on google or yahoo when you wanted to sign up for a new email account.

Okej, some extension to the smtp-protocol is then needed and this is somewhat inconvenient for the sender but the bussiness oportunities for a spamming company would be drastically worse if they had to have employees just do the pattern recognition for each email sent.