Яков Светский

Судя по всему, в SPF записи добавлен параметр include:spf.protection.outlook.com, а запись TXT на поддомене outlook.com по каким то причинам уже убрали, в результате чего SPF и выдает ошибку

Нет, ошибся, 2whois.ru не увидел запись на поддомене, а nslookup и остальные сервисы видят. Как вариант что то обновляли и информация не успела распространиться по интернету

Если отправка идет с почтового клиента, вкратце процесс выглядить так (возьмем например почту на майл ру и почту получателя info@krutayafirma.com):
1. клиент отправляет письмо на сервер майл ру
2. сервер майл ру посылает запрос в DNS-зону домена krutayafirma.com, узнать почтовые сервера этого домена (MX-записи)
3. Из MX-записей выбирается запись с наименьшим приоритетом и сервер делает туда запрос - info@krutayafirma.com - есть такой ящик?
4. Если сервер не ответил, берется следующая по приоритету MX-запись и запрос повторяется
5. Если сервер получателя говорит есть, письмо отправляется туда
6. Спам фильтры сервера получателя анализируют письмо, и решают, отправить его во входящие, в папку спам или вообще отфутболить обратно

В gmail.com к любому ящику можно привязать миллионы алиасов. Во первых он не воспринимает точки между буквами логина, то есть mylogin@gmail.com, my.login@gmail.com и m.y.l.o.g.i.n@gmail.com это один ящик.
Символы после знака+ тоже не воспринимаются, то есть на тот же ящик придет письмо если где то укажете почту mylogin+vol123@gmail.com
Если же говорить о корпоративных почтах со своим доменом - на том же Yahoo Small Business можно создать до 30 алиасов, на Migadu десять создавал как то, но помоему вообще нет ограничений, надо потестить

Решение с Exchange добавит промежуточных звеньев в Вашей почте, плюс дорогое.
У яндекса последнее время есть недоработки, тоже не самый лучший вариант. Могу предложить два варианта других (G Suite тоже не рассматриваю по причине стоимости).
Во первых Майл Ру для бизнеса, легко переносится с яндекса со всем содержимым, тоже родные приложения, жалоб на нее у пользователей гораздо меньше. Также беплатная и без ограничений по размеру ящиков. Плюс гораздо более оперативная поддержка, среднее время ответа меньше суток. Яндекс мне как то осенью отвечал больше месяца!!! Сразу уточню, при переносе организацию в яндекс коннекте лучше удалить, а то яндекс так и продолжит отправку писем с других ящиков яндекса себе, не глядя на MX.
Второй вариант платный, и более экзотический. Швейцарская Migadu. Без своих приложений, придется использовать сторонние, достаточно простой веб интерфейс. Но четко работающая. На всех платных тарифах неограниченное количество почтовых ящиков, неограниченное количество доменов, нет ограничений по объему. Цены зависят от количества отправляемых писем в день со всех ящиков. До 100 исходящих в день - 5 долларов в месяц, до 500 - 17 долларов, до 2000 - 60. Причем органичение не жесткое, если превысите, придет письмо - не хотите ли поменять тариф. Если выберите этот вариант могу попросить у них промокод. Уже давали, но помоему он закончился.
Оба варианта можно пробовать на отдельных небольших по количеству почт доменах и сравнивать.