Добрый день!
Сталкивался много раз с такой проблемой, перечислю самые частые причины:
1. Неправильно прописанные DNS - множество ошибок бывает. Прописывают запись TXT для самого домена. Запись должна быть прописана для поддомена (селектор)._domainkey (например у яндекса mail._domainkey, у майл ру mailru._domainkey). Часто запись или не полностью копируют, или например прилипает пробел в конце. Добавляют поддомен вместе с доменом, что то типа mail._domainkey.domain.com и запись прописывается для mail._domainkey.domain.com.domain.com
2. Часто запись вступает в силу не сразу. Например для того же яндекс коннекта бывают задержки до недели
3. Было пару раз, что DKIM настраивали для почты на хостинге, а письма отправлялись не через почту, а напрямую php, естественно DKIM тоже не работал