Для начала, вы какой приватный ключ используете для DKIM? Смущает то, что вы пишете, что запись в DNS прописал вам Яндекс, а не вы, но при этом рассылаете то вы со своего сервера. Т.е. вы должны были либо взять приватный ключ, который вам сгенерил яндекс (который можно получить только при обращении в саппорт), либо таки использовать свой, но тогда вы должны были и создать вторую запись публичного ключа для DKIM в DNS, чего, судя по вашему тексту, вы не делали.