Alterar os nomes dos servidores internos, como sugerido por MichelZ , é uma opção, mas pessoalmente, acho mais fácil adicione um monte de nomes ao campo SAN (Subject Alternative Names) no certificado para ficar muito mais fácil.
O servidor corporativo do Exchange que eu gerencio, por exemplo, tem 17 SANs no certificado - portanto, há 18 nomes que os usuários podem usar para acessar o servidor de email sem gerar um erro de certificado.
De qualquer forma, verifique se o certificado está carregado em ambos IIS e Exchange, embora.