В техподдержку писали, переписывались и обоюдно решили, что проблема в Престашоп. Так решили по причине того, что письма отправляемые с обычного почтового ящика приходят и никаких проблем нету. В СПАМ приходят только письма, которые отправляются через админку, т.е. тестовое письмо, письма о заказе и т.д.