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:
X-Hashcash: 0:030626:adam@cypherspace.org:6470e06d773e05a8
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.
[1] http://www.hashcash.org/
