Unable to open Outlook

We've got a user who keeps getting an error saying "The set of folders cannot be opened. The attempt to log on to Microsoft Exchange has failed." I've tried creating a new email profile via control panel, which succeeds but still throws the error when you open Outlook. I've reinstalled Office 365, turned off MFA, and reset his password.

I've also tried setting up the same user's email account on my own computer and gotten exactly the same error.