Gmail marks email from my server as spam

Question

I'm configuring a new mail server, but have trouble with the e-mail: gmail marks it as spam. I've checked all the obvious things (SPF, DKIM, Reverse DNS, IP adress blacklisted or known spammer). OS is Debian 7 wheezy (rc-2) and MTA is exim4. Exact same message is not marker as spam from current mail server.

The gmail message is something like "looks like spam based on content" (don't have it at hand), but that is strange as the email with almost the same content goes trough if my main mta is used.

I don't know what I can check anymore, does anyone know what is going wrong?

The headers of a message are as follows:

Delivered-To: somegmailadress@gmail.com
Received: by 10.231.19.205 with SMTP id c13csp30281ibb;
        Thu, 2 May 2013 13:57:59 -0700 (PDT)
X-Received: by 10.14.100.1 with SMTP id y1mr24043617eef.9.1367528278598;
        Thu, 02 May 2013 13:57:58 -0700 (PDT)
Return-Path: <root@karolina2.sintjansbrug.nl>
Received: from karolina2.sintjansbrug.nl (karolina2.sintjansbrug.nl. [149.210.129.77])
        by mx.google.com with ESMTPS id g47si9932355eem.247.2013.05.02.13.57.58
        for <somegmailadress@gmail.com>
        (version=TLSv1.2 cipher=RC4-SHA bits=128/128);
        Thu, 02 May 2013 13:57:58 -0700 (PDT)
Received-SPF: pass (google.com: domain of root@karolina2.sintjansbrug.nl designates 149.210.129.77 as permitted sender) client-ip=149.210.129.77;
Authentication-Results: mx.google.com;
       spf=pass (google.com: domain of root@karolina2.sintjansbrug.nl designates 149.210.129.77 as permitted sender) smtp.mail=root@karolina2.sintjansbrug.nl;
       dkim=pass header.i=@sintjansbrug.nl
DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=sintjansbrug.nl; s=sjb;
    h=Content-Type:MIME-Version:Message-ID:Subject:To:From:Date; bh=Ccc4FRDI9WGZkTIFmUXwyCQ++Xa+9o/z/+IaeiXjS4s=;
    b=NXjcr0uLHdeGWZd/8u4zOTWSO7O3uNymchBHNBrcS6Atrfb3iwtB0lurznJ242lLSHdzihdTNSOusO1ep+sCeiX4ojST2iVvES5fijwD8S/QM2V2XYRm0LJFH/3aaOnfkJNNQYyIhB5vPf92qyVsXQRzh5o4mi1VcP8waRy8Bg7wU3eSxOTcloCNxE7so868Eu0TxW/6H6u9lKoAjQjuVeqXXfVaCLB/XrRBkTjNETHhgn8cRobEtKzZ8GAlY7WRJDbp3HVrKyMHmJFW6vkg3fZFLkEW/W4b5VD2PnK80H7nifVDYcBk/vmnJdSrT+PPbUwFPCEbkqoTjJ0Cd9m66F6YdkEwPVJgcCQ09zyqFXHVrJOuSqT0FCsh4qb0NiasSt/8mgDFxfHHYVLu2MbyJuR3j6cwQnbyWRHbMQ6SDamFdyFC0f3Rk1H1SeVKgtaWSnp+s5ngt9PKDkIEriEBMZSSmXzIhTXcapP/F5GmOcQQC0MyPT7S1SOJ9254S0Iac5rBHHM9XmYiYFyci9u5iWE3Zt19m0MY30ustczVMHNjOy+89dUy1ue5xInPOE+iJs/IOqB96e8HcSTwz7Kret+Z2c0koK61c/0I81wOG4WiRAqTEjNjivo/rI068pai87x1O+90Ziu4zi00Hl5Q/IN97bhuxT/yQdbuJZuaGCU=;
Received: from root by karolina2.sintjansbrug.nl with local (Exim 4.80)
    (envelope-from <root@karolina2.sintjansbrug.nl>)
    id 1UY0Zi-0005Zm-5T
    for somegmailadress@gmail.com; Thu, 02 May 2013 22:57:58 +0200
Date: Thu, 2 May 2013 22:57:58 +0200
From: root <root@karolina2.sintjansbrug.nl>
To: somegmailadress@gmail.com
Subject: This is a test message
Message-ID: <20130502205758.GA21427@karolina2.sintjansbrug.nl>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
User-Agent: Mutt/1.5.21 (2010-09-15)

I do not know what went wrong

Answer 1

I suspect you are hitting an IP reputation filter. Many ISPs now use IP reputation to help determine if email is spam or not.

I see messages hit the spam folder if:

• No Sender History
• Poor Sender History
• Poor IP Range

I checked your IP over at SenderScore and SenderBase and suspect the issue is related to the first problem.

Google has not seen email from your IP before, so it may be treating it as spam until they can trust your IP is not a spammer.

Also your IP could have been flagged in the past as a spam source is and is still in there.

You may need to file a removal/investigation request with Gmail.

https://support.google.com/mail/contact/msgdelivery

I have a tutorial on the process here. http://www.rackaid.com/resources/gmail-blacklist-removal/