Verifique se eles estão em uma lista negra: link
Então o remetente tem um registro PTR? Caso contrário, eles devem ter problemas ao enviar para vários domínios.
O usuário pode enviar e-mails para outras pessoas no seu domínio? Se assim for, então é provável que o seu computador de alguma forma.
Você provavelmente terá que trabalhar com o provedor de TI, já que realmente precisa atacar esse problema do lado do remetente e rastrear o e-mail. Pode não ter nada a ver com seu servidor, mas pode ser bloqueado antes mesmo de deixar seus sistemas por algum motivo.