O mxtoolbox tem um verificador de lista negra bastante abrangente. Eu sei que você já checou, mas isso pode ser útil para outras pessoas que se deparam com esse post também.
Sua melhor aposta - como mencionado pelo caelyx - é implementar DomainKeys e acabar com todo esse absurdo. Yahoo e Gmail, ambos djim luz verde assinaram e-mail até que eles tenham razão para fazer o contrário (usuários marcando spam). Se isso é relacionado a negócios, é um ROI bem óbvio. Uma hora ou mais de configuração e teste equivalem a muito menos problemas com filtros de spam.