We run into this often, so thought it would be good to share if anyone else runs into this.
Older Office 365 accounts are *NOT* set up to do modern authentication by default. So if the tenant was created prior to the change of default, you must do it manually. Otherwise, Outlook will keep trying basic authentication despite you having enabled two factor authentication.
To do this through the GUI you can go here:
If you prefer doing it through Powershell:
Set-OrganizationConfig -OAuth2ClientProfileEnabled $true
