Email going to Gmail and Hotmail SPAM (OVH VPS)

[apinto]

Greetings,
All outgoing email from Sentora VPS is going to Gmail/Hotmail Spam folders.
They are NOT blocked, they just get stuck on the spam folder.

Gmail says: It’s similar to messages that were detected by our spam filters.
From my search this error might mean it is related to the content, I've tried various content with the same spam result.
Also I'm not sending newsletters, it's just regular company email.

MX Toolbox Lookup: http://mxtoolbox.com/SuperTool.aspx?acti...n=toolpage
Mail Tester Results: https://www.mail-tester.com/web-GchJNE

I'm using SPF and DKIM TXT Records (Cloud Flare DNS):

Code:

;; TXT Records
mydomain.pt. 300 IN TXT "v=spf1 +a +mx +a:mail.mydomain.pt +ip4:92.222.17.48 ?all"
dkim._domainkey.mydomain.pt. 300 IN TXT "v=DKIM1\; p=MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDY4g4WKznTI3ubNkKz/AFKgYqWbhIn5gj8cGy9nFX0J6B7dlhte6kTrtLVEJmNl7MvlJnGve+C1+TCmRvitY5QNauoyafjbmhB3Cm50RbVJy6LgenarCiEIxoPPeizVgbSpZaSh0ow9eCa/YAzjJAchFBl9TpoT04ZfnxA8yzKewIDAQAB"

On Cloud Flare the main domain (A/AAAA record) is CloudFlare enabled, the mail subdomain is using a A record and not Cloudflare enabled.

Also I tried this with another domain and same results.
IP is not blacklisted.

Anyone can give any tips to troubleshot the issue?
Thank you!