Just relay it out via a trusted host, in addition to setting up DKIM, SPF, etc.; that solved all the problems for me. My email server is working excellent for many years now (OpenBSD, OpenSMTPD, dovecot) with Rainloop as web-based frontend.
Is DMARC included in your 'etc'? I think thats needed for gmail these days. If rdns, dkim, spf and dmarc are there, try checking your IPs reputation (senderscore) that could be it.