Depois de tentar corrigir esse problema por dois dias, deparei com a ferramenta Analisador de configurações do Microsoft Office, conhecida como OFFCAT.
link
Vendo que não tinha nada a perder, baixei e instalei o software.
OFFCAT varreu o Outlook e notou que estava faltando cerca de duas atualizações para o Outlook 2013 e uma para o próprio Office. Junto com uma chave de registro que não era padrão.
Não sei qual das correções resolveu o problema. No entanto, depois eu consegui me conectar para trocar e configurar o perfil do Outlook normalmente.
Obrigado a todos que ofereceram conselhos.