Похоже, это связано с тем, что я начал использовать Google DNS в качестве своих серверов пересылки.
Ваш DNSBL вообще ничего не блокирует! Сначала проверьте ответ на часто задаваемые вопросы «Ваш DNSBL блокирует весь Интернет!» и убедитесь, что вы не сделали орфографическая ошибка в конфигурации вашего почтового сервера.
Проверьте, какие DNS-преобразователи вы используете: Если вы используете бесплатный "открытый DNS-преобразователь, например Google Public DNS или Public DNS Level3. серверов для разрешения ваших запросов DNSBL, в большинстве случаев вы получите ответ «нет в списке» (NXDOMAIN) от общедоступных серверов DNSBL Spamhaus. Пожалуйста, используйте свои собственные DNS-серверы при выполнении DNSBL-запросов к Spamhaus.
Источник: http://www.spamhaus.org/faq/section/DNSBL%2520Usage#261