Emails retorno failing for a long time

Amigos,

Venho tendo um problema a um tempo com um cliente.

O mesmo faz um grande envio de e-mails para hotmail, e em geral chega bem, o problema é que muitos dos funcionários da empresa anotam ou enviam para o endereço errado e fica dando aquelas mensagens de usuário não existe etc.

O problema que por conta desses erros, de uma hora para outra começa a não enviar mais nenhum e-mail para @hotmail.com apenas quando remoto os e-mails da retry.

Mensagem de retorno:

This message was created automatically by mail delivery software.

A message that you sent could not be delivered to one or more of its
recipients. This is a permanent error. The following address(es) failed:

umexemplo@hotmail.com
all hosts for 'hotmail.com' have been failing for a long time (and retry
time not reached)

Parece que ha algum limitante de se falhar tantos % ou quantos e-mail para um determinado endereço ele começa a rejeitar todos.

Alguém tem alguma idéia?