Hi Stefan,
Did you get a chance to test with other versions of Outlook like Outlook for Microsoft 365 to check the result?
Do you have a custom domain or this a default "onmicrosoft.com"-based email address?
From what I know, for Office 365 users who aren't F plan users, it's supported to configure the account to Outlook 2013. I've also tried to test in my lab and managed to add an onmicrosoft.com account to Outlook 2013(RTM):
For current situation, please use the I need help setting up my Office 365 email in Outlook diagnostic in the Support and Recovery Assistant (SaRA) tool to run an automatic check and see if it will return any possible solutions.
Furthermore, here is an official article for your reference. As Autodiscover has been checked and it was successful, I'd like to suggest pay more attention to other methods like the Method 4 about checking the user's attributes in AD.
If an Answer is helpful, please click "Accept Answer" and upvote it.
Note: Please follow the steps in our documentation to enable e-mail notifications if you want to receive the related email notification for this thread.