As for "validating" the rest of the email headers, well... I want to strike a balance between "sure you can do that, good luck!" and "the entire anti-spam community has tried this and it is basically impossible, which is why we rely heavily on IP reputation and Bayes-based approaches which do not treat the contents of the headers as semantically meaningful, since they are in the hands of the enemy".
Step 1: If DKIM header present, then use result of DKIM validation.
Step 2: If sending domain has SPF record, then use result of SPF validation.
Step 3: If message passes SPF check using a conservatively guessed SPF record, then treat the message as valid.
Step 4: If message came from same IP address as other messages for user and some headers match headers from previous messages (fuzzy match on message id?), then treat the message as valid.
Step 5: What next? Messages will make it past the previous steps.
DKIM, which is not widely deployed, typically protects the message, From: and To: headers, and other headers. If this is actually used, you only have to worry about replayed messages (a hacker sends 1,000,000 copies of a legitimate blog post), which is doable. Unfortunately, you can't do anything if this header is not present - even if I have a Yahoo/GMail/... address, which would otherwise be DKIM'ed, I may have sent this message via another mail server.
SPF, which checks that the server sending the mail is authorized to do so, would work reasonably well, or at least hand off the issue to the administrator of the sending mail server. Unfortunately, there are quite a few domains without SPF or which SOFTFAIL all; worse, prank-loving coworkers may have access to the same mailserver.
"Same IP address" falls afoul of the pranking coworkers again, and is a very weak heuristic anyway.
There are at least two solutions that work. The actually secure one is requiring the user to PGP- or S/MIME-sign all mail; the other one is to send back a challenge. Mailing lists managers typically do this - send a message with "Subject: 23dsaf2: please confirm post" and accept any response that contains 23dsaf2 in the subject.
It's OK that DKIM is not widely deployed because the logic falls back to other mechanisms when the DKIM header is not present. DKIM is deployed on GMail and Yahoo Mail, so it is worth doing. Replay attacks are easy to defeat by not posting duplicate content. It's probably a good idea do to dup detection to handle the case where the user accidentally sends the message twice.
Yes, I agree that DKIM+duplicate detection is fairly good; you just can't rely on it being present, and if it isn't you have to fall back to much less reliable stuff.
It's structured in a way that makes it very easy to snip out the parts you want to use without necessarily using all the rest.
Plus this validates the OPs question. It's not hard to receive emails somewhere, but it is hard to clean them, validate the sender with SPF and a few other email non-standards.
I've been using google app engines email service but it chokes and rejects a ton of emails that I forward to it.
Maybe Posterous could spin off an email cloud service? It'd be a distraction from their core competency, but I could see a lot of value.
If you're going to validate with headers then feel free to call it usable but don't call it security.
If a server allows multiple people to send from the same address, then you can't validate further than that.