Longo Prazo
A questão chave aqui é qual é o risco associado à inclusão de seus e-mails na lista negra?
Se o risco potencial em termos de impacto nos negócios for significativo, pagar por serviços de e-mail gerenciados é um bom investimento.
Com hospedagem compartilhada, há riscos significativos para a entrega de emails. Sistemas sobrecarregados, contas hackeadas, outras pessoas enviando newsletters e atividades similares diminuem a reputação de envio do IP. Frequentemente, faixas inteiras de IPs são marcadas como suspeitas.
Problema atual
Em termos de resolver a situação atual, entre em contato com seu host. Envie-lhes quaisquer relatórios de grandes listas negras ou exemplos de rejeições dos principais ISPs.
Existem muitas listas negras, mas a maioria que você encontra em sites de verificação de listas negras não é amplamente usada. Spamhaus, Spamcop, Barracuda e serviços similares são aqueles que podem bloquear seu email para um grande número de usuários.
Além das pesquisas na lista negra, verifique a reputação do remetente no SenderScore: link
Diferentes anfitriões respondem em vários assuntos, mas quanto mais clara a evidência que você pode fornecer de que eles têm um problema de grande impacto, maior a probabilidade de eles agirem.