Isso acabou sendo um problema de configuração do DNS. Por alguma razão que eu nunca vou entender, este cliente estava usando um arquivo de host local para resolver certos nomes de domínio. Uma das entradas aqui incluía o nome do host do servidor de correio interno, mas apontava para um endereço IP antigo. Essencialmente, o Outlook tentou procurar o endereço interno e recebeu um IP, por isso assumiu que deveria ser conectável. Não foi. Remover esta entrada antiga resolveu o problema.
Quanto ao problema de domínio / não domínio: quando os técnicos de TI no site configuram um computador de domínio, eles enviam esse arquivo de hosts como parte de seu processo de implantação. Quando testei com um novo computador, não usei o processo de implantação, por isso não recebi o arquivo hosts.
Mistério solucionado.