В DNS есть TXT-запись с именем "mail._domainkey"?
Домен точно делегирован на DNS яндекса?
"пробовал самостоятельно добавить DKIM запись в DNS" - что именно прописывали? Публичный ключ откуда брали?
Если оповещения нужны для всех папок, можно попробовать отдельное правило "вывести оповещение" для всех подряд входящих писем, а после него уже следующими правилами раскладывать по папкам.