I have a VPS on my dedicated server at OVH. It's a carefully configured Postfix with Webmin, I have SPF, DKIM and other stuff, I'm not on any RBLs (and I have Nagios watching the RBLs continously). No mass email, spam or marketing is sent from that machine or any other 16 IP addresses I own. Yet still every time I email a new contact in Gmail my email goes to spam.
Today someone asked me to help them with emails sent from Joomla on their EC2 instance. I just typed apt-get install postfix and the email just arrived to the inbox in gmail. No SPF, no DKIM, no configuration of any kind - and it had better rating than my carefully configured server with 2 years history of sending legitimate emails.
I don't like Amazon, though. QUESTION: what other companies can I move the VPS to and have great IP reputation?