Emails marked as spam - SPF passes, DKIM passes, sender-id passes

Question

I've been struggling to figure out why this is happening, but my emails are being marked as spam by Gmail and Hotmail (they work in Yahoo.)

SPF, DKIM, rDNS, and sender-id all pass. What's weirder is I've send the EXACT same email with its exact contents from my dev server and Gmail accepts it as not spam even though every one of those checks which passes in production fails in dev. Hotmail still marks it as spam though.

Any idea what could be going on? Here is an example header from Gmail (with IPs and domains changed for privacy):

Delivered-To: [email protected]
Received: by 10.194.16.130 with SMTP id g2csp192349wjd;
    Mon, 13 Aug 2012 14:04:10 -0700 (PDT)
Received: by 10.236.193.105 with SMTP id j69mr12819871yhn.21.1344891849751;
    Mon, 13 Aug 2012 14:04:09 -0700 (PDT)
Return-Path: <[email protected]>
Received: from mail.mydomain.com (mydomain.com. [xxx.xxx.xxx.xxx])
    by mx.google.com with ESMTPS id e22si563514yhh.132.2012.08.13.14.04.08
    (version=TLSv1/SSLv3 cipher=OTHER);
    Mon, 13 Aug 2012 14:04:09 -0700 (PDT)
Received-SPF: pass (google.com: domain of [email protected] designates xxx.xxx.xxx.xxx as permitted sender) client-ip=xxx.xxx.xxx.xxx;
Authentication-Results: mx.google.com; spf=pass (google.com: domain of [email protected] designates xxx.xxx.xxx.xxx as permitted sender) [email protected]; dkim=pass [email protected]
Received: from mydomain.com (localhost [127.0.0.1])
by mail.mydomain.com (8.14.4/8.14.4/Debian-2ubuntu1) with ESMTP id q7DL48tq019625
for <[email protected]>; Mon, 13 Aug 2012 17:04:08 -0400
X-DKIM: OpenDKIM Filter v2.3.2 mail.mydomain.com q7DL48tq019625
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=mydomain.com;
s=server; t=1344891848;
bh=lpw+5POmINBjQYgQBdJvY2d+m84MY8hwTqZ6riNfH8I=;
h=Date:From:To:Message-ID:Subject:Mime-Version:Content-Type:
 Content-Transfer-Encoding;
b=KnYSvSzFewOGFyYWvP1DfCvyRfp6y31BfOPTOgRsZ7nGB4PXuau84euzuhs82V4lx
 ++DjN3iPxSj07euW+y7aRe9R2YiXKJFVNh7cbcJX8+tc3LMmnR7Cv27iP3Yvv6mQMd
 uz4Engql3bXLVVDKcLLj/Fj2eiwtWzW4chA2GNTQ=
Received: (from root@localhost)
by mydomain.com (8.14.4/8.14.4/Submit) id q7DL48Dm019624
for [email protected]; Mon, 13 Aug 2012 17:04:08 -0400
Date: Mon, 13 Aug 2012 17:04:08 -0400
From: "Website" <[email protected]>
To: [email protected]
Message-ID: <[email protected]>
Subject: You've received a message from Bob.
Mime-Version: 1.0
Content-Type: text/html;
charset=UTF-8
Content-Transfer-Encoding: 7bit
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=mydomain.com; q=dns/txt; s=server; t=1344891848; bh=LfadLl6eJEB+NgiTbBlcBhOt/9NKcG0wapkrAjlGqfg=; h=content-transfer-encoding:content-type:date:from:message-id:mime-version:subject:to; b=mTB8TBb+gG7ESxeVbfqHANKUMeNbdwK/hSIq58oin5ERNSMKOIvZKY9cQJRoY/Q96PQ7J+7b3ZkZuwcg+zMkQyhK7YACvFAz4SUWqpdqiZrBDw8Vqy3PjkGFcz2V5vyUOjI6vN/Y6iOj1zlocC+/p8lkpw3upwxr7cNoe5/Kwu8=

Solution

The other guy doesn't know what he's talking about and just guessing.

'Received: (from root@localhost)' is your problem. That needs to reflect the from email...