Почтовые сервера. У всех все норм?

Запустили рассылку прайсов, и встретились с проблемой:

This message was created automatically by mail delivery software.

A message that you sent could not be delivered to one or more of its

recipients. This is a permanent error. The following address(es) failed:

Причем, от них, с этих же ящиков получаем письма с вопросами и подтверждениями, а в ответку отправить не можем.

Причем для проверки отправляли с мейла и рамблера... Та же история.

Таких мейлов больше 15 шт

На 95% уверен, что это проблема с их стороны (раз мейл и рамблер не смогли помочь)

Вопрос: Как наладить нормальное почтовое отправление, или какие советы дать нашим клиентам в настройках (тк почты разные, разные сервера и тд)

Заранее спасибо.