It seems like spam is in the news every day lately, and frankly, some of the proposed solutions seem either completely hare-brained or worse than the problem itself. I'd like to reiterate a relatively modest proposal I first made over a year ago: Require legitimate DNS MX records for all outbound email servers.
MX records are one component of a domain's Domain Name System (DNS) information. They identify IP addresses that accept inbound email for a particular domain name. To get mail to, say, linux.com, a mail server picks an MX record from linux.com's DNS information and attempts to deliver the mail to that IP address. If the delivery fails because a server is out of action, the delivering server may work through the domain's MX records until it finds a server that can accept the mail. Without at least one MX record, mail cannot be delivered to a domain.