メールサーバーでIPv4とIPv6の両方を有効にしていると、GMailは優先的にIPv6で接続するようです。
GMailで迷惑メール判定されないようにするためには、下記条件を満たす必要があります。
1) 送信元ドメイン認証（SPFまたはDKIM）に対応する
2) メール送信元ドメインがDNS逆引きできるように設定する
運用中のサーバーがIPv6を有効にしていましたがIPv6逆引きに対応していなかったため、メールサーバー側でIPv6接続を禁止する必要がありました。
Postfix 2.8移行の場合は、/etc/postfix/main.cf に下記設定を追加します。
smtp_address_preference = ipv4
こうするとIPv4を優先して接続するようになります。
Postfixのバージョンが古い場合は下記のようにIPv4のみで接続するように設定します。
inet_protocols = ipv4