Emails from my domain treated as spam by Gmail and Outlook

Question

I know that this question asked multiple times before but I have a little bit different situation.

In Brief:

I have reverse DNS, PTR records, SPF records, DKIM 1024-bit key, IP not blacklisted, message content not spam characteristics.

Emails delivered to inbox on Yahoo and AOL. but, they go to spam / junk on Gmail and Outlook.

---

In details:

Reverse DNS checked:

host 12.34.56.789

Note: This IP isn't the real IP of the server.

Output:

789.56.34.12.in-addr.arpa domain name pointer mydomain.com.

SPF records:

"v=spf1 +a +mx +ip4:12.34.56.789 -all"

SPF Checked by mxtoolbox:

DKIM Checked by protodave:

IP blacklist test checked by mxtoolbox: Passed All

Yahoo and AOL works fine, but Gmail and Outlook mark emails as spam.

I contacted the gmail team couple of times but they didn't respond for over 10 days.

I'm sending plain text, no html codes.

No bulk emails, no newsletter.

Does anyone have a solution for this issue? Am I missing something? Appreciate any suggestions.

---

Further Details (Email Header):

Delivered-To: [e-mail]
Received: by 10.202.86.147 with SMTP id k141dre728845oib;
        Tue, 4 Nov 2014 23:26:11 -0800 (PST)
X-Received: by 10.170.225.135 with SMTP id r129mr14547913ykf.104.1412359371276;
        Tue, 04 Nov 2014 23:26:11 -0800 (PST)
Return-Path: <[e-mail]>
Received: from hostname.mydomain.com (mydomain.com. [12.34.56.789])
        by mx.google.com with ESMTPS id v44si1322694yhv.201.2014.11.04.23.26.10
        for <[e-mail]>
        (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128);
        Tue, 04 Nov 2014 23:26:10 -0800 (PST)
Received-SPF: pass (google.com: domain of [e-mail] designates 12.34.56.789 as permitted sender) client-ip=12.34.56.789;
Authentication-Results: mx.google.com;
       spf=pass (google.com: domain of [e-mail] designates 12.34.56.789 as permitted sender) smtp.mail=[e-mail];
       dkim=pass header.i=@mydomain.com
DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=mydomain.com; s=default;
    h=Content-Transfer-Encoding:Content-Type:MIME-Version:Message-ID:Subject:From:To:Date; bh=lr4CWwmBPE2kmCn+bQZxuDI83bEg03tG585GFUO9nbM=;
    b=gsXWNQFoHVg/98V1pfGYpqCmzeKE6BK/93Zy/vT61ySaEdeLrTl9TW6Ca8C/nh+1C19vRfQbv716c+Q2gDEfAXw5/S8mEPjoBAlF96bXfLUuIpnY2OLLELAobd+VkpYaeOpAVnVMUDoie5M+m+lp98btL31BXWOKfPCCJ8UHZ5Q=;
Received: from localhost ([::1]:36366 helo=www.mydomain.com)
    by hostname.mydomain.com with esmtpsa (TLSv1:DHE-RSA-AES256-SHA:256)
    (Exim 4.82)
    (envelope-from <[e-mail]>)
    id 1Xluyo-00032t-Az
    for [e-mail]; Wed, 05 Nov 2014 02:26:10 -0500
Date: Wed, 5 Nov 2014 02:26:10 -0500
X-Priority: 3
MIME-Version: 1.0
Content-Type: multipart/alternative;
    boundary="b1_73e9fc0155fddc64feb30693a746sd5c"
Content-Transfer-Encoding: 8bit
X-AntiAbuse: This header was added to track abuse, please include it with any abuse report
X-AntiAbuse: Primary Hostname - hostname.mydomain.com
X-AntiAbuse: Original Domain - gmail.com
X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12]
X-AntiAbuse: Sender Address Domain - mydomain.com
X-Get-Message-Sender-Via: hostname.mydomain.com: authenticated_id: [e-mail]

--b1_73e9fc0155fddc64feb30693a746sd5c
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit