Ваш сервер не считается отправителем почты по их фильтру спама? Потому что я предполагаю, что они могут получать почту от других людей.
Так что я думаю, вам нужно посмотреть на настройку вашего сервера, чтобы он соответствовал их квалификации (например, обратимое имя или любые другие правила, которые требуются от отправителя электронной почты)
Поскольку с помощью PHP (и других языков) вы просто отправляете электронную почту, существуют инструменты, которые отправляют электронную почту через другой сервер, который подходит для отправки электронной почты, но обычно вы используете сам сервер.
Например, вы можете использовать библиотеку Zend Mail для отправки через другой SMTP-сервер.