Você pode aumentar sua credibilidade em relação a outros servidores por
- usando DKIM para assinar seus e-mails
- definindo uma política do SPF apropriada
- fazendo verificações de vírus em emails de saída
- tente ir muito longe de um servidor de e-mail compartilhado porque eles podem arruinar todos os seus esforços
- usa um serviço de terceiros que mantém uma reputação melhor ao ser proativo contra spam, como o Mandrill, o SendGrid, o Postmark, o Amazon SES, etc.
P.S. Esta lista está aberta para adições