Přesně stejný problém jsem řešil také. Pozadal jsem o vypis informaci od jejich SpamAssassinu, a jedno z pravidel, které mě spolehlivě posílalo do spamu, bylo HELO_DYNAMIC_IPADDR -- IP adresa serveru je z rozsahu dynamicky pridelovanych adres.
Vyřešil jsem to přeposíláním pošty přes SMTP server svého providera (do konfiguráku Postfixu jsem přihodil relayhost=[smtp.provider.cz]) a je po spamizaci mých mailů. Přináší mi to jiný problém, Postfix má tendenci takhle posílat i lokální maily (jako třeba na adresu user@localhost), ale to už je jiný problém -- zatím jsem neměl moc času se tím nějak extra zabývat...