Для правильного вопроса надо знать половину ответа
Запись надо добавлять на NS-сервере вашего домена. Но для начала надо определить, почему не доходят письма. Отсутствие SPF-записи всего лишь одна, и не самая вероятная из возможных причин.
Вячеслав: Если письма не принимаются севером mail.ru, то должны возвращаться письма с текстом ошибки. Если принимаются, но попадают в спам, надо смотреть причину.
Простой
