Parece que está relacionado ao fato de que comecei a usar o DNS do Google como meus encaminhadores.
Your DNSBL blocks nothing at all! First, check our FAQ answer for "Your DNSBL blocks the whole Internet!" and make sure you've not made a spelling mistake in your mailserver configuration.
Check what DNS resolvers you are using: If you are using a free "open DNS resolver" service such as Google Public DNS or Level3's public DNS servers to resolve your DNSBL requests, in most cases you will receive a "not listed" (NXDOMAIN) reply from Spamhaus' public DNSBL servers. Please use your own DNS servers when doing DNSBL queries to Spamhaus.
Fonte: link