recently gmail implemented something called "SPF verification" (or something). It checks the senders domain SPF record and if it hase one verifies that the mail really came from an authorized mail server.
In my orginazation we have a mailserver that also runs the ecartis mailing list software. The server thus relays an incoming email to all subscribers of the list.
Unfortunatly this means that gmail shows a possible phising message on every email where the domain has an SPF record (primarely @gmail.com itself).
Is there any way to solve this other than maybe a clumsy workaround like relaying all @gmail.com messages back to the gmail SMTP servers?
Create an SPF record for your domain via cPanel or whatever DNS management panel you use. Specifically, an SPF record is simply a TXT record.
Google outlines how to add an SPF record to your domain for webmasters in your plight in a help article.
Don't use the default "google.com" they have though. Look at this article to see which would fit your website the best. I assume you're sending mail through your MX servers, so I would use...
v=spf1 mx ptr -all
Of course, your website configuration may vary.