In part 2 of my Ubuntu mail server set up guide on Linode I wrote about my experience with Gmail soft failing all emails sent from my server and my work around of just using Google Apps to send my mail. Such a solution works well if you are only dealing with end-user accounts however I have recently had to use the system SMTP server to send out emails for my online password keeper application, Passbook.
The solution to getting your emails out of Gmail's spam filter and into users' folders is to set up a SPF TXT record. You can do this by using the Open SPF wizard or just use the settings below in your Linode DNS Manager.
To create those settings simply add a new TXT record and leave the name empty and use "v=spf1 a mx ~all" as the value. What that TXT record means is that it is a SPF record saying that for your domain all servers pointed to by an A or MX record can send emails on behalf of your server. The ~all means that any other server that sends email on behalf of your domain may or may not have permission to do so. To disallow any other hosts from sending email with an @yourdomain.com address use -all and to allow use ?all.
After you make these changes you can query whether they have worked using dig @ns1.linode.com TXT yourdomain.com from a *nix command line. The answer section should show the TXT record. You will need to wait for this data to propagate (I waited about 3 hours) before testing by sending a brand new email to your Gmail account. The email needs to have a new subject and message so that Gmail does not flag it as being the same as a previously marked spam message.