Postfix: Gmail marking my email as spam
Apparently after a few days it start working fine.
Right now, I guess what really matters in GMAIL is actually passing this tests:
SPF check: pass
DomainKeys check: neutral
DKIM check: pass
Sender-ID check: pass
SpamAssassin check: ham
And wait 3 or 4 days so google can update their servers. Seems like the spam filter does some kind of internal cache on DKIM and SPF lookups for a particular domain.
UPDATE: This problem seems to be back, I've no ideia how to fix it.