NXDOMAIN означает, что запись mail._domainkey не существует, или по крайней мере, ваш DNS-сервер о ней не в курсе.
Скорее всего, запись добавлена некорректно, или вообще не добавлена, или добавлена, но называется иначе, например default._domainkey.
Короче говоря, проблему надо решать с тем, кому делегирована ваша зона.