Existem alguns sites que executam um conjunto automatizado de testes contra seu servidor de e-mail para problemas, como este:
http://mxtoolbox.com/blacklists.aspx
e há outros sites que verificarão o endereço IP de um servidor de e-mail em relação às listas de bloqueio reverso (RBLs).
http://www.rbl-check.com/
Se você estiver listado em uma RBL, quase sempre receberá uma URL para visitar com os detalhes da sua transgressão.
Eu enviaria seu servidor de e-mail para ambos.