O problema é simplesmente um problema de resolução de DNS. O MTA de recebimento não tem uma resolução de DNS confiável ou seus servidores DNS são escamosos. Sem saber qual domínio mydomain.tld
realmente é, é impossível para qualquer um determinar se o último é o caso, mas quanto mais domínios do destinatário enviarem esse erro, menos provável será o primeiro.