Meu servidor de e-mail está sendo considerado como spam pelo GMail e Yahoo

Pessoal,
os envios de e-mails através do meu servidor está indo diretamente para a caixa de SPAM do GMail e Yahoo.
Envio apenas textos simples, sem links, sem imagens e sem anexo.
O problema é que o e-mail não retorna dizendo que é SPAM, chega normalmente ao usuário mas diretamente na caixa de SPAM.
Nos LOG's diretamente do servidor não aparece nenhum erro, nenhum problema. Da como enviado normalmente.

Meu servidor de e-mail é um Linux Debian com o serviço postfix, amavis e spamassassin.

QUais soluções implantas no seu server?

SPF, Greylist, DomainKeys?

Gostaria de saber se a mensagem apenas vai pra caixa de spam ou a mensagem eh marcada como spam com {spam} na frente. se nao vem marcada pode ser apenas um filtro de um usuario, se nao for isso, vc pode estar numa lista do mailserver do yahoo por algum motivo. se a mensagem for marcada verifique se seu ip tah numa blacklist como alguma da spamhaus.
envie uma mensagem pro yahoo e post o log dela, pra gente ver.

É bem provavel que voce não tenha uma das soluções.

SPF, Greylist, DomainKeys, Dkfilter.

Verifique isso