A chave para solucionar esse problema é fazer com que alguém analise os logs da transação SMTP de saída no servidor do remetente. Você pode tentar correlacionar suas falhas com seus próprios logs de controle de mensagens, logs de protocolo SMTP ou sniffing de tráfego, mas os melhores dados virão do próprio servidor SMTP do remetente. Se o remetente tiver uma equipe de TI, recomendo trabalhar para entrar em contato com eles. Caso contrário, tente fazer com que o remetente forneça os relatórios de falha na entrega com os cabeçalhos completos de transporte.
Você precisa saber em qual servidor SMTP o remetente está realmente tentando realizar a entrega e, a partir daí, você deve ser capaz de rastrear a origem do problema. Se eles estão conversando com um servidor que você controla, então você deve ser capaz de obter um log da conversa SMTP, possivelmente todo o caminho até um farejamento de tráfego. Se eles não estão falando com um servidor que você possui, então você precisa descobrir por que eles não estão (ou seja, cache DNS obsoleto).
Pesquisas de DNS em cache para momentos totalmente inapropriados não são completamente desconhecidas, mas também não são comuns. Se você souber quem o remetente está usando para um servidor DNS upstream, tente fazer algumas pesquisas de registros MX para o seu domínio em relação a esse servidor DNS para ver o que você recebe de volta.