O MX ToolBox é uma ótima ferramenta para essas situações. Ele verifica todos os seus registros DNS e outras configurações comuns. Ele também pode verificar a maioria das listas de bloqueio do endereço IP do seu servidor.
Vá para o link e digite seu endereço IP. Isso faz o diagnóstico básico de SMTP.
Após a execução, você verá um link para a lista negra na parte inferior da transcrição. Clique para verificar as listas de bloqueio.