In a nutshell, I have tried rebooting his system, re-creating new user profiles for the user, even re-installed office on his machine. What's strange is that the user is able to connect after creating a new profile, but then the same issue comes back after a few days, and the user cannot reconnect again.
I am going to run the SARA diagnostic tool and send results to MS support, but was hoping if anyone here has run into this isssue before. This is only happening to this 1 user. I have verified that his network connection isn't the issue, as he's able to connect to web pages and use Teams.
The user is also able to access mail via Outlook web app no problem, so this issue really looks like his desktop app.
I have two users experiencing this same issue. They're both on Azure and their web portal outlook works fine, but we keep getting this re-occurring issue with the desktop app. The only solution we've gotten to work so far is removing and re-adding their account. But it is only a temporary fix and the issue re-occurs within 3-14 days. I don't have any other solutions for you sadly, just wanted to add in that you are not going crazy or the only one having this issue.