Была аналогичная проблема.
Проверьте не находится ли выданный Вам IP-адрес в листе блокировки?
Если адрес заблокирован хотя бы в одном листе, то пишите в поддержку. Они конечно будут говорить, что это не взаимосвязано, но настаивайте на своем - сменят.
Согласен с
Сергей , необходимо тщательно изучить логи, попробуйте поискать по слову "abuse".
Постмастеры, в моём случае, просто писали что письма никакие не получали, а Мэйлган твердил обратное. Как искать письма между ними я так и не понял :)