Q:

Google marks seemingly perfect emails as spam

First post - was directed here from stackoverflow!
The problem: Google marks seemingly correctly formatted emails from my apache/postfix server as spam. Sample email as follows;
(I have replaced my domain with mydomain.com.au and the IP with a pretend IP)
Delivered-To: my.email@gmail.com
Received: by 10.150.216.21 with SMTP id o21cs22383ybg;
        Fri, 26 Feb 2010 23:11:55 -0800 (PST)
Received: by 10.231.152.75 with SMTP id f11mr1470919ibw.50.1267254715619;
        Fri, 26 Feb 2010 23:11:55 -0800 (PST)
Return-Path: <apache@mydomain.com.au>
Received: from mydomain.com.au (mydomain.com.au [80.107.158.80])
        by mx.google.com with ESMTP id 29si1651619iwn.31.2010.02.26.23.11.54;
        Fri, 26 Feb 2010 23:11:55 -0800 (PST)
Received-SPF: pass (google.com: domain of apache@mydomain.com.au designates 80.107.158.80 as permitted sender) client-ip=80.107.158.80;
Authentication-Results: mx.google.com; spf=pass (google.com: domain of apache@mydomain.com.au designates 80.107.158.80 as permitted sender) smtp.mail=apache@mydomain.com.au
Received: by mydomain.com.au (Postfix, from userid 48)
    id ACB735030340; Sat, 27 Feb 2010 18:11:53 +1100 (EST)
To: my.email@gmail.com
Subject: Quote for David Brent (00125512123)
From: quotes@mydomain.com.au
Reply-To: quotes@mydomain.com.au
X-Mailer: PHP/5.2.10
Message-Id: <20100227071153.ACB735030340@mydomain.com.au>
Date: Sat, 27 Feb 2010 18:11:53 +1100 (EST)

Name: David Brent

Mobile: 00125512123

Phone:

Email: my.email@gmail.com

Date: 2010-20-21

Time: 21:00

Location: Syd

Eventype: Musicians

Message: Yep, this should work!!!!

how did you hear about us: Newspaper

I have tried sending it to non-google emails, and they arrive fine.
I have tried posting to several different google accounts, all end up as spam.
Mydomain.com.au uses Google Apps as email provider.
I have added "v=spf1 a mx ~all" as TXT in my NS.
I used http://remote.12dt.com/ to check reverse DNS and the IP seems to be resolving back to the domain name just fine.
My IP is not blacklisted in spam-lists (as far as my checks can tell). I host at www.jumba.com.au - in Australia.

The headers seem fine, and the SPF look up seems to pass (?).. Any ideas?
Kind regards

A:

mxtoolbox has a pretty comprehensive blacklist checker. I know you already checked but this might be useful to others who come across this post as well.
Your best bet - as mentioned by caelyx - is to implement DomainKeys and be done with all this nonsense. Yahoo and Gmail both green light dkim signed email till they have reason to do otherwise (users tagging it spam). If this is at all business related it's a pretty obvious choice ROI wise. An hour or so of configuration and testing equals much fewer issues with spam filters.

