GMailでスパムメールになってしまう時にチェックしたいこと

SPF への対応は、GMail側での受信チェックだけでよければ、DNSの設定だけでOKです。 評判のさくらのVPSでSMTP(Sendmail)を公開する時にやっておきたいこと 「DNSの正引きの設定を行う。」でのSPF設定を参考に対応をしてみてください。
DNSの設定情報は、Sender Policy Framework (SPF) の仕組み を参照してください。
メールの受信側の対応は、sendmail で smf-spf を使ってSPF認証する を参照してください。

設定を終えたら、GMailのアドレスへメールを送信してみましょう。

上記のように、受信したメールのヘッダ情報に pass が出力されていればOKです。

DKIM への対応は、SMTPサーバーの設定とDNSの設定が必要になります。sendmail で dkim-milter を使ってDomainKeys ,DKIM の対応する を参考にDKIM への対応を行ってみてください。

WHOIS情報は、ドメインレジストラで設定できます。ドメインレジストラで確認し、もし、変な情報が設定されているなら、修正しましょう。
また、WHOIS情報のチェックは、今では、いろんなサイトでチェックできます。
ここでは、http://www.cybersyndrome.net/whois.html を紹介しておきます。

1. http://www.cybersyndrome.net/whois.html (WHOIS) へアクセスします。
   
   

   ここで、ドメイン名 を入力し 検索ボタンをクリックすれば、WHOIS情報が出力されます。
   

   
   
2. WHOIS情報が出力結果を確認します。
   
   

   このようにWHOIS情報が出力されます。内容を確認し、空欄などになっていないか各項目を確認しましょう。
   全ての情報が設定されていて、メールアドレスなどが有効なアドレスになっていればOKです。
   

   
   

レンタルサーバーの場合、独自ドメイン名を逆引きのホスト名に設定することはできないこともあります。 ( さくらのVPSではできます。 参照 : 評判のさくらのVPSでSMTP(Sendmail)を公開する時にやっておきたいことの「DNSの逆引きの設定を行う。」 )
ここでも逆引きができるは、必ずしも独自ドメインである必要もありません。単純にIPアドレスからホスト名が確認できれば良いので、nslookupで確認できればOKです。

$ nslookup
Default Server:  web.setup
Address:  xxx.xxx.xxx.xxx

> server 8.8.8.8
Default Server:  google-public-dns-a.google.com
Address:  8.8.8.8

> yyy.yyy.yyy.yyy
Server:  google-public-dns-a.google.com
Address:  8.8.8.8

Name:    wwwxxxxu.sakura.ne.jp
Address:  yyy.yyy.yyy.yyy

>

ここでは、問い合わせるDNSサーバーをGoogleが公開しているDNSサーバーにし、自SMTPサーバーのIPアドレス( ここでは、yyy.yyy.yyy.yyy としています ) を入力し Name 情報にちゃんとホスト名が出力されればOKです。

BlackListのチェックは、今では、いろんなサイトでチェックできます。
ここでは、http://www.mxtoolbox.com/blacklists.aspx を紹介しておきます。

1. http://www.mxtoolbox.com/blacklists.aspx (Blacklists Check) へアクセスします。
   
   

   ここで、IPアドレス を入力し Blacklist CheckボタンをクリックすればIPアドレスがBlacklistに登録されていないか診断が始まります。
   

   
   
2. 診断結果を確認します。
   
   

   このように診断結果が出力されます。STATUS OK なら大丈夫です。
   チェックされるのは、147のBlack Listについて診断されます。
   

   
   

SMTPサーバーの設定が、正しくできているかチェックしておきます。
ここでは、単純なメール中継チェックをしてくれるページ ( Mail relay testing)を紹介しておきます。

1. http://verify.abuse.net/relay.html (Mail relay testing) へアクセスします。
   
   

   ここで、Address to test: メールサーバ名（ホスト名）を入力し test for relay ボタンをクリックすれば診断が始まります。
   

   
   
2. 診断結果を確認します。
   
   

   このように診断結果が出力されます。全部で17項目のチェックが行われます。
   もし、診断結果に異常が検出された場合は、その項目で中断します。
   

   
   

   上記のように 17項目のチェックの後、All tests performed, no relays accepted. が出力されればOKです。
   

   
   

ほとんどの場合は、受信者にてスパム解除を行うことで、同じアドレスからも送信時には、スパム扱いされなくなります。
ただし、SMTPのサーバーを切り替えたり、同じドメインでも別のユーザ名からのメールに関しては、相変わらずスパム扱いされるかもしれません。

受信者にてメールフィルターを設定してもらうのも一つの手段です。あるいは、メールアドレスをアドレス帳に登録すれば、同じような効果を得ることができるでしょう。

Googleさんへ問い合わせは、
Gmail Help — Report a problem with a message
から行うことができます。ただし、英語のみです。