Sort of like SPF, which has some issues, mostly regarding forwarding and mailing lists. Setting up a domain doesn't take all that much time, and I believe I read somewhere that said spammers are the primary source of registering new domains. Newer domains are more likely to be spam, and so spamassassin marks domains that were created within the last day or so as more likely spam.

I think it is really hard to change the SMTP protocol, and have it be implemented all over the place. Certainly, you can increase the "score" of a spam if it doesn't implement your strategy, but if you take a look at all the different methods people have tried to implement, they haven't really gone very far. (SPF, hashcash, domainkeys, etc).

Also, your first scenario (the bouncing back to X) if Y's mail server is misconfigured. If Y delivers the spam to someone who didn't send it, he is now at fault, and should be treated as a spammer. There is no excuse (well, there's one, but I don't think it counts) for bouncing a message to someone who you don't know if they sent it (or worse, bouncing a message because you think it is a virus to someone who you definitely know didn't send it, since that is how the virus works)
SpamCop started accepting spam reports a couple years ago for mail servers that were incorrectly configured. I think some places have fixed their servers, but there are many that are still misconfigured. The more they get reported, and blacklisted, the more motivation they have to fix their servers.

http://www.spamcop.net/fom-serve/cache/329.html

I'm not sure I track what you're saying exactly. In fact, I've probably misunderstood.

Are you saying a person would need to set up a password with an external spam checking service for each email address that they create, which would check a user-supplied password for each email (or for a single login?) Are you essentially asking that people log into their email service twice, which would be more secure than logging in once? Or have I misread you? Probably.

... Personally, I wonder why Cpanel offers features to help screen out spam from others (somewhat poorly), but doesn't do much to identify when servers have been hijacked for spam. That would seem to be an easier task. Yahoo has such features. A simple Captcha (read this weird text to prove you're human) if you trip the alarm would probably go a long way. Those who own servers have some incentive not to be blacklisted as spammers and implement this. Why don't the existing filters simply point in both directions on more machines?

First, Jon, thanks for the intelligent comments. The nice part about the first idea is that it wouldn't be so much a change to existing SMTP protocol per se (the token could be added as an SMTP header) as it would be an additional optional step on each end.

As mentioned, on the client side, that step could be carried out by a relatively simple SMTP proxy. On the sever side, servers like Qmail already have pluggable evaluation steps, where the additional check could be carried out.

To clarify for Ryan, and others I've probably misled: No, I'm saying that domain hosts (people hosting domain, say, xyz.net) would install an additional piece of software for validating e-mail messages as non-spam.

When I go to read my mail, I *already* have to supply a password to get into the POP3/IMAP which delivers my mail to me. All I'm proposing is that you install another piece of software right "next door".

To spell out the steps in more detail:

1. I type in my e-mail message from me (tim@sender.foo) to Bob (bob@receiver.foo), and click "send".

2. My e-mail clients is configured (perhap via proxy) to generate a unique random "token" (just a string of random characters) which it tosses into an extra field on the message.

3. My client ALSO contacts my domain's e-mail validation server (located on the same box as sender.foo's SMTP server), logs in with a password (I don't see this or have to think about it, it just does it automatically) and informs it about the random token and destination.

4. My e-mail client sends rest of the message as usual: It contacts the destination STMP server (at destination.foo) and transmits the message.

5. When destination.foo receives my message, it notices it allegedly comes from tim@sender.foo, looks up the SMTP server associated with domain sender.foo, contacts the validation server running on that host (anonymously -- no login required, the port # is well known too) and asks: "Hey: Did tim@sender.foo send a message with token XL4q90xZ5 to bob@receiver.foo?" My e-mail authenticator service say, in its best June Cleaver voice: "Well, yes, he did. How nice of you to ask!" After this, milk and cookies are offered.

6. The mail delivery agent for receiver.foo can then confidently dump my message into Bob's box, knowing full well that the alleged sender REALLY did send said message -- as opposed to someone else simply pretending to be that person.

And, certainly, as mentioned above, one could register entire spam domains. But they could easily be traced to the registrar, and the registrar could trace them to the one doing the registering. And if the registrar didn't choose to do that final step, spam-conscious ISP could start disallowing all mail from domains associated with "loose" registrars.

Being as most of these spam processes installs a SMTP server to send the spam messages under its own processes your method would be ineffective. The spam process would just add the "token" to the message and approve it when the authentication request came back. I understand what you are trying to say with this, but it just wouldn't work, to easy to get around considering how spam is usually sent from the zombie machines.

Only allowing SMTP messages from their own servers is a better solution, but not perfect either. For instance I have several email addresses, some of them are on my ISP's domain, some of them are on my work domain, and some still are on my own domain, so I am never on the domain of all three, as such how do I send my emails? Why shouldn't I be able to send my work email from home and my home email from work?

Being as most of these spam processes installs a SMTP server to send the spam messages under its own processes your method would be ineffective. The spam process would just add the "token" to the message and approve it when the authentication request came back.

The final SMTP server (the one which ultimately delivers it to the end-users mailbox) would check the token with the SMTP server specified by the DNS entry for the sender's domain.

I have several email addresses, some of them are on my ISP's domain, some of them are on my work domain, and some still are on my own domain, so I am never on the domain of all three, as such how do I send my emails?

I think this was answered already:

let's say I'm visiting Japan, am using an unfamiliar public network, and wish to send mail to you. In the first step, my mail program talks to my own domain (in some secure, password-enabled fashion) and gets or sets a token which allows mail to be sent from me today. Then, my mail program attaches that to the message and sends it along. Next, the recipient host receives the message, contacts my domain, and asks if the given token could have come from me, and, only if so, delivers it.