Почта gmail.com в блэк-листе в dnsbl.sorbs.net, как быть, мои пользователи жалуются что от gmail почта не идет?

Нет, "не удалось" - это как раз таки код возврата sorbs.net о том, что проверяемый адрес найден в одном из списков:
new.spam.dnsbl.sorbs.net 127.0.0.6
recent.spam.dnsbl.sorbs.net 127.0.0.6
old.spam.dnsbl.sorbs.net 127.0.0.6
spam.dnsbl.sorbs.net 127.0.0.6
escalations.dnsbl.sorbs.net 127.0.0.6

Почта gmail.com в блэк-листе в dnsbl.sorbs.net, как быть, мои пользователи жалуются что от gmail почта не идет?

Сразу спама много сыпаться начинает. Проверял уже.
Да и логически-то это должна быть проблема гугля а не моя.