For instance, if you always sent mail and asked Facebook (or, hm, OpenSocial), "Hey, give me proof that so-and-so knows me?"
Then, if Facebook signed that request using some simple PKI system, you'd include the sig in your email header, and you could verify it's not spam using PKI. (Twitter, etc. could do the same thing.)
It could be possible to roll this kind of thing into an Outlook plugin, and webmail systems could follow fast with OAuth implementations of the same thing. You could deploy this widely within 12 months, and your mail would get through, very reliably.