A Customer just forwarded me this which is more or less a confirmation that Google (and Sunrise who uses Google Mail Services) do penalize emails from domains with no SPF:
http://www.google.com/support/a/bin/answer.py?hl=de&answer=33786
"Wenn für Ihre Domain kein SPF-Datensatz vorhanden ist, werden Nachrichten von Ihren Nutzern möglicherweise von einigen Empfängerdomains abgelehnt, da nicht bestätigt werden kann, dass die Nachrichten von einem autorisierten Mailserver stammen."
Hm, nope, I read this differently: this is targeted towards google customers, and apparently google recommends them to define an SPF record for their domain, because some _other_ mail servers might penalize their mail if they don't.
IMHO SPF is broken by design, and the possible problems far outweigh the small benefits. I've seen again and again problems caused by non-SPF-aware mail redirects, and this is something completely outside the realm of influence of the domain owner. How can you know whether an email address you're writing to is in fact a redirect to another email address? You can't. All those mails will be submitted using a 3rd party mail server as the sending source, which will backfire if the domain defines a too restrictive SPF record. And why would a server that doesn't consider SPF useful go the length of performing source rewriting?
Everyone is allowed to configure his/her mail server to reject incoming mail based on whatever they consider reasonable. This of course includes the right to refuse mail from any host called "banana" or if the checksum of the subject is 13. Hell, you can even use SPF if you want. Does this lead to reliable mail delivery? No. Is it forbidden? No. Does it make sense? You decide.
Cheers, and sorry for the rant, Markus