Целый час мучался с дебагом spf записи. Оказалось, при замене redirect на include забыл = заменить на : Обычная невнимательность. На такие ошибки больше всего времени тритатися.

Ошибка была здесь:

v=spf1 include=_spf.yandex.ru include:mxsmtp.sendpulse.com +a +mx ~all

А должно быть:

v=spf1 include:_spf.yandex.ru include:mxsmtp.sendpulse.com +a +mx ~all

+a и +mx можно не добавлять, это дефолтное значение.

Для дебага spf записей удобные сервисы:
https://mxtoolbox.com/SuperTool.aspx?action=spf
https://www.kitterman.com/spf/validate.html?