Se um reparo do Office não ajudar, e a configuração / desativação do Firewall do Windows não ajudar, esse problema pode ser devido a um arquivo corrompido do Windows.
Para verificar se há arquivos corrompidos do Windows, use o Verificador de arquivos do sistema Windows digitando o seguinte em um prompt de comando do administrador:
sfc /scannnow
Isso resolveu o problema para mim, e o Outlook conseguiu enviar mensagens novamente dessa máquina.
Beginning system scan. This process will take some time.
Beginning verification phase of system scan.
Verification 100% complete.
Windows Resource Protection found corrupt files and successfully repaired
them.
Nota: mesmo se você usou o SFC antes, consulte o link, pois ele inclui algumas informações adicionais úteis sobre o log SFC e ações que você pode realizar se o SFC disser que encontrou um arquivo corrompido, mas não conseguiu corrigi-lo .