O mesmo problema aqui com a mesma configuração (Exchange 2003 + ESET NOD32 + Fortigate). Quando alguém tenta nos enviar e-mail e receber esse erro, adicionamos o domínio à lista de permissões do fortigate e isso resolve o problema. Isso provavelmente significa que o firewall envia os e-mails.
A lista de permissões pode ser gerenciada em UTM - > Filtro de E-mail - > Endereço de email Você pode aceitar ou rejeitar e-mails com base no endereço do remetente, você pode usar wilcard (*@gmail.com) ou regexes.
No nosso caso, tivemos que colocar na lista de permissões apenas uma dúzia de domínios. Não sei ao certo o quanto isso seria dimensionado para milhares de domínios.