Multi-factor Authentication breaks outlook

I actually dealt with a similar issue today where a users Outlook would stay at "Disconnected" in the bottom right while outside of our whitelisted network IP range. Our organization turned on Multi-Factor auth through the modern Azure portal about 3 months ago. We had prepared the organization by making sure the https://support.office.com/en-us/article/Enable-Modern-Authentication-for-Office-2013-on-Windows-devices-7dc1c01a-090f-4971-9677-f1b192d6c910 were being pushed out via group policy AND confirming that our machines were patched with the latest Office 2013 patches (that should get the required files to the right versions; https://support.office.com/en-us/article/Plan-for-multi-factor-authentication-for-Office-365-Deployments-043807b2-21db-4d5c-b430-c8a6dee0e6ba?ui=en-US&rs=en-US&ad=US in the "MSI-based installations" section). Today we began enforcing multi-factor auth through the classic Azure portal https://techmymindsite.wordpress.com/2018/01/15/legacy-authentication-the-achilles-heel-of-azure-conditional-access-v2-0/. That's when this behavior began - the user simply could not connect when outside of our white-listed network. 

I ran the https://www.microsoft.com/en-us/download/details.aspx?id=36852 and this pointed me in the right direction. It turns out that I was missing the files that the patches mentioned above should have installed. I installed those missing KB's (in this case, the Csi.dll and MSO.dll files were missing from the C:\Program Files(x86)\Common Files\Microsoft Shared\OFFICE15\ directory) and it connected finally.

Another red flag that you should keep in mind is when you setup an Outlook profile OR your user is prompted for their password (in your case after changing the password), that the password box is the basic username/password box. This means your client is attempting to connect with Legacy/Basic Auth, instead of modern auth. Make sure your https://support.office.com/en-us/article/Enable-Modern-Authentication-for-Office-2013-on-Windows-devices-7dc1c01a-090f-4971-9677-f1b192d6c910 are set AND you https://support.office.com/en-us/article/Plan-for-multi-factor-authentication-for-Office-365-Deployments-043807b2-21db-4d5c-b430-c8a6dee0e6ba?ui=en-US&rs=en-US&ad=US

Modern Auth Prompt GOOD:

Legacy/Basic Auth Prompt (attached) BAD