Адреса для email рассылки то валидны, то нет, как это решить?

Столкнулся с проблемой, при валидации email адресов ряд из них (example@mail.ru, example1@gmail.com, example2@yandex.ru) проходят валидацию.
При первой рассылке по этим адресам вылетает soft/hard bounce.
При повторной - всё ок.
В чем может быть проблема?