Postfix Email appearing as SPAM to GMail
So I run my own hosting company and have done for some years. I recently decided to take the decision to ditch Plesk for various reasons and give ISPConfig 3 a try.
I successfully setup my own cluster of servers, 6 in total, Panel, DNS 1, DNS 2, Web, Mail, DB all running on Ubuntu 12.04 LTS.
Everything is working perfect except for my mail server which has a very peculiar problem. Everything is working fine with incoming and outgoing email except for outgoing email via Postfix to GMail accounts (I guess Hotmail and Yahoo could be similar but I am concentrating on GMail at the moment). This issue is happening with all domains, not just one inparticular.
rDNS and SPF are set correctly. I have run blacklist tests and the mail server IP is clean (there is only one IP). The hostname is set correctly too.
After running various tests, I have discovered the following.
1) If I setup the account as IMAP on a client such as Windows Live Mail with and without SSL turned on for outgoing mail, then any emails sent to a GMail account land in the GMail SPAM folder.
2) If I use SquirrelMail to send an email to GMail then again the email lands in the GMail SPAM folder.
3) If I setup the IMAP account on an iphone with SSL turned on then the email gets delivered to the GMail Inbox as you would expect it to.
1, 2 and 3 above are all being sent from the same IP address (then sent to the postfix mail server as any normal setup) via my broadband connection (the Iphone is connected to wireless) so that cannot be the reason seeing as scenario 3 delivers the email correctly.
All 6 servers are in a data centre and are not hosted within a local home network.
After comparing the headers of each of the emails with scenarios 1 (With SSL on) and scenarios 2 and 3 they are exactly identical apart from the section that explains the email was sent was from an Iphone for scenario 3 and from Windows Mail for scenario 1 and SquirrelMail for scenario 3.
Outgoing authentication is turned on for all scenarios as Postfix will not allowing relaying without authentication using the account username and password for the email account setup.
I believe I have checked and covered everything that I can except for something that may be wrong with the PostFix configuration in some way or something I have missed.
After reading many many forum posts both on this site and others I was starting to believe it was just GMail being picky as it does and having to wait over time for them to start allowing emails from the server to the Inbox rather than flagging as SPAM but when analyzing the headers the SPF passes, rDNS is set correctly and why did the Iphone mail (yes going through the same mail server as all scenarios) land in the Inbox?
As you can tell I am confused to say the least and would appreciate any help in solving this so I can put my new infrastructure into production.
Thank you in advance.