Eu já vi isso acontecer algumas vezes antes e aqui estão as causas que eu vi. Tenha em mente que estes só foram vistos em um ambiente grande. Se você estiver em um único ambiente de servidor dc e exchange único, estes não serão aplicados.
Primeiro, aqui está o artigo da Microsoft sobre isso: link . Sob as cuases possíveis, você pode ver que há muitas coisas em jogo.
Uma das suas permissões de retransmissão de servidores de troca não está configurada corretamente.
Essa é a causa mais provável. O e-mail pode estar tomando uma rota diferente na primeira e segunda tentativa, enquanto isso pode soar bobo executando rastreamento de mensagens em ambas as mensagens, veja se eles passam pelo mesmo servidor. Se você vir diferentes caminhos, verifique as configurações no caminho ruim, pode ser um simples permitir que a retransmissão para usuários autenticados não seja verificada.
As permissões do AD estão erradas
Você deve ter permissões Enviar como na conta que possui o endereço de do seu e-mail. Se estiver funcionando às vezes, mas não em outros, pode haver caminhos diferentes no roteamento de e-mail, com permissões diferentes entre eles.
A autenticação não está funcionando corretamente.
Na primeira instância do script, pode ser que a autenticação falhe e, nesse caso, o email é negado, pois você não tem permissão. Na segunda execução do script, a autenticação é bem-sucedida. Infelizmente eu não conheço o ASP suficientemente bem para entender o código acima ou aconselhar sobre como corrigi-lo. smtpClient.UseDefaultCredentials pode não ser o código correto para o seu ambiente. Isso só será autenticado se solicitado pelo servidor e usará as credenciais do usuário conectado localmente. Se o servidor não estiver solicitando autenticação na primeira vez, você não será autorizado e poderá não ter permissão para enviar. Tente alterá-lo para algum código que sempre autentique.
Um de seus DCs ou catálogos globais está desatualizado ou tem informações incorretas.
Isso é raro, mas é possível que seus controladores de domínio tenham informações fora de sincronia. Verifique as informações do servidor de e para contas via ldap ou adsi edit e verifique se elas são idênticas em todos os dcs.
Em todas as instâncias, verifique os logs no servidor do Exchange e certifique-se de que o log do SMTP esteja habilitado em todos os campos. Use o rastreamento de mensagens para ver exatamente quais servidores esta mensagem está atingindo.