Eu estava tendo esse mesmo problema para um usuário específico no meu domínio e, além de definir corretamente a permissão "Enviar como" na guia Segurança da caixa de correio do usuário em questão, você também deve garantir que o usuário que será enviando como a caixa de correio ser adicionada aos direitos de caixa de correio da caixa de correio.
Para esclarecer:
1) Abra a caixa de correio em questão
2) Clique na guia Exchange Advanced
3) Clique em Direitos da Caixa de Correio
4) Adicione o usuário do AD que estará enviando e-mails como esta caixa de correio
5) Assegure-se de que o acesso completo à caixa de correio esteja selecionado para o usuário
6) Clique em Aplicar e OK
7) Teste se você pode agora enviar-as do cliente Outlook do usuário depois de esperar que o Exchange aplique a alteração
Espero que isso ajude,
Jason S.