I'm using postfix, and have setup spf, dkim, and domainkeys. I can get my email to go to Yahoo, but not gmail. Here's the headers from an email send to Yahoo. Yahoo reports the email as domain key verified.
X-Apparently-To: brianegge at yahoo.com via 68.142.206.167; Sat, 20 Mar 2010 05:29:19 -0700
Return-Path: <domains at theeggeadventure.com>
X-YahooFilteredBulk: 67.207.137.114
X-YMailISG: x7_Rl9EWLDuugoqPcORhih0FeQMOaIIpz4qfuu9ttx1xbo3uKI2kz.CLUy2cJ1BTtHAwuJtrsGRsveHIx.Dx95avNGlPPGWy_cSpnEwWLXGxBciO.YgtSQxdURQiWLCLvbHej0QPjQIHFjAFjdeGhJd2Y8NgTW1wcExq45Sb7LMlOGvtGMjSQuc8QazwXUxpZrQbIxgSQUTmzQO1x30xaZ2Us6TQTab7Wpya6OgAX.emKOM3phfS5kfhYj9FLQ.qi32sFNWnAoFdVK596OTP2F63PAJOVM5qPsM2jIAbJylIBmnj94LO7hOVr3KOS6XLtCPRn2Oe
X-Originating-IP: [67.207.137.114]
Authentication-Results: mta1055.mail.mud.yahoo.com from=theeggeadventure.com; domainkeys=pass (ok); from=theeggeadventure.com; dkim=pass (ok)
Received: from 127.0.0.1 (EHLO mail.theeggeadventure.com) (67.207.137.114) by mta1055.mail.mud.yahoo.com with SMTP; Sat, 20 Mar 2010 05:29:19 -0700
Received: by mail.theeggeadventure.com (Postfix, from userid 1003) id BB5B01C16A4; Sat, 20 Mar 2010 12:29:16 +0000 (UTC)
DomainKey-Signature: a=rsa-sha1; s=2010; d=theeggeadventure.com; c=simple; q=dns; b=JHbK9VhqyQTfpQFqaXxJrKpEG9h9H0IZ0LdWoBooJEA7hv3SYWmFUtyE247EuwoaG gzApKJ1DuRhwESZ7PswrbzuaUL8poAUO8LmMvZ+OqnDolgNSJUYWu0FcO+fe3H4m9ZD grkj0xMpHw+uFjXV4plKO+sa8olJXJAmP+9cMEo=
X-DKIM: Sendmail DKIM Filter v2.8.2 mail.theeggeadventure.com BB5B01C16A4
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=theeggeadventure.com; s=2010; t=1269088156; bh=bUlMldcnzFCmCmNT8qjpRl6fiY1YyjiZiC9jhCXASOw=; h=Subject:To:Message-Id:Date:From; b=EVNolTlh4Gch5/HIrrHaRQvcApl7wkB42gB44NsPcLZD2QrhuOvnhanhnEB4UbV0e A+3dAOjhX7LKzgGrn11jXNTiEjNX1vQDsX3HyG0fNra73aWiGTzr1nHJfnuEJ7Ph0j 5tp0HRL5jjikD1XJcvmsYzTpT22mxuz60HXYRB1s=
Subject: cron
To: <brianegge at yahoo.com>
X-Mailer: mail (GNU Mailutils 1.2)
Message-Id: <20100320122916.BB5B01C16A4@mail.theeggeadventure.com>
Date: Sat, 20 Mar 2010 12:29:16 +0000 (UTC)
From: This sender is DomainKeys verified domains@theeggeadventure.com (domains) View contact details
Content-Length: 818
When I send to gmail, I see the following in my server log, but the message doesn't even reach my spam folder.
Mar 20 12:59:12 Everest postfix/pickup[27802]: C81C61C16A4: uid=1000 from=<egge>
Mar 20 12:59:12 Everest postfix/cleanup[27847]: C81C61C16A4: message-id=<20100320125912.C81C61C16A4@mail.theeggeadventure.com>
Mar 20 12:59:13 Everest postfix/qmgr[27801]: C81C61C16A4: from=<egge@theeggeadventure.com>, size=2784, nrcpt=1 (queue active)
Mar 20 12:59:14 Everest postfix/smtp[27849]: C81C61C16A4: to=<brianegge at gmail.com>, relay=gmail-smtp-in.l.google.com[209.85.223.24]:25, delay=2.1, delays=0.39/0.28/0.13/1.3, dsn=2.0.0, status=sent (250 2.0.0 OK 1269089954 32si4566750iwn.51)
Mar 20 12:59:14 Everest postfix/qmgr[27801]: C81C61C16A4: removed
I've send to email to test services, and the report everything verifies ok. I've also checked all the RBL lists, and I'm not on any of them.
Best Answer
I'm not sure if this is your exact problem, but I experienced something similar, and in my case I was able to solve it by setting up a Reverse DNS entry for my mail server's IP. That way a receiving SMTP server can verify that a message sent from your server's IP can be resolved to the same domain name as the "From" address in the SMTP header. (I could be wrong on some of the details.)
Google seems particularly picky about that, even if you've also set up SPF and DomainKeys.