Оказывается теперь Яндекс еще может не отправлять письма с "подозрительных" аккаунтов.
Пол дня промучился с настройкой, в итоге написал в саппорт, на что получил ответ:
Данная проблема вызвана тем, что регистрация Вашего логина показалась подозрительной нашей системе безопасности.
Чтобы устранить проблему с отправкой и получением писем, необходимо указать на странице https://passport.yandex.ru/passport?mode=passport достоверные персональные данные. Там же необходимо будет привязать мобильный телефон (ссылка «номера телефонов»), если Вы этого еще не сделали и, в случае, если появляется запрос капчи (контрольных символов), ввести ее. После этого блокировка снимется автоматически.
Обратите внимание, что для снятия блокировки потребуется несколько часов - за это время система должна получить и запомнить внесённые Вами изменения.