Одна проблема - если домен попал в спам, то довольно высока вероятность, что он оттуда уже не вылезет.
Лучше всего поменять IP, прописать PTR, SPF, DKIM, все пункты из
Bulk Senders Guidelines и молиться :)
Вообще если так и не получается вылезти из спама, можно попробовать внешние сервисы рассылки (типа Sendgrid и прочих)