Um código de resposta 4.x.x é um código temporário, portanto, o Exchange continuará tentando até que o intervalo de novas tentativas expire. O que você pode tentar é instalar um programa de captura de pacotes no servidor do Exchange (o Microsoft Network Monitor é bom) e iniciar uma captura e deixá-lo rodar por um tempo. Você pode configurar um filtro de captura para capturar apenas o tráfego SMTP e DNS para manter a sobrecarga de captura baixa. Depois de executar uma captura, envie um email para um usuário em um dos domínios problemáticos ou espere que um email atualmente enfileirado tente novamente (ou force uma nova tentativa) e veja o que aparece na captura, digitando o tráfego DNS primeiro para ver se as coisas estão sendo resolvidas corretamente ou não e, em seguida, passar para o tráfego SMTP para procurar pistas sobre o que está acontecendo.