Outlook with Basic Authentication
Outlook stores the password itself when you choose the Remember my credentials option. It uses the saved information as long as it doesn't work anymore. This is authentication method is unable to use Windows credentials, so every users needs manually update the passwords.
Kerberos Authentication
The Microsoft Exchange Team Recommendation: Enabling Kerberos Authentication for MAPI Clients by Ross Smith IV explains Kerberos authentication and tells how it has changed in Exchange 2010. This may be the cause the authentication was working as you remembered but doesn't do so now:
Typically, domain-joined clients/applications either leverage NTLM or
Kerberos for authentication. The actual authentication mechanism used
depends on the configuration of both the client and the server and
they negotiate the authentication to be used during the establishment
of the connection. MAPI supports Kerberos authentication and the
default setting in Outlook 2007 and later is to negotiate the
strongest authentication available when not running in Outlook
Anywhere mode.
In Exchange 2010, MAPI clients connect to load-balanced array of
servers, and not an individual server with its own unique network
identity. This change in the messaging architecture presents a
challenge, however. In previous Exchange versions, clients connected
directly to the Mailbox server which was a single identity on the
network. This meant that the client, if capable, could utilize
Kerberos authentication for establishing the session with the Mailbox
server.
The recommendation is to deploy alternate service account (ASA) credential mechanism to enable Kerberos authentication for MAPI clients. See the article for detailed information.
The steps to deploy the ASA credential are as follows:
- Create an account to be used as the ASA credential.
- Deploy the ASA credential to the CAS members.
- Convert the OAB virtual directory to an application.
- Assign the SPNs to the ASA credential computer account.
Office 365 Modern Authentication
Just for completeness, Kerberos authentication is only possible with on-premises Exchange Server. However, Office 2013 (and later) and Office 365 supports Active Directory Authentication Library (ADAL) sign-in. See Using Office 365 modern authentication with Office clients.