@Bruce Jing-MSFT I have discovered that the AutoDetect service was the core of the problem, but not in the way I would expect.
The AutoDetect service is used by the Outlook Mobile app to act as the "AutoDiscover of AutoDiscover's". Which means that instead of the app connecting directly to the AutoDiscover URL of the Exchange server (as has been the case for most of Exchange's history, and is still the case for the iOS Mail app), the AutoDetect service does this and relays the information to the app.
This means that if the AutoDetect service cannot reach the AutoDiscover service on the Exchange server, it will time out and fail. Which is exactly the issue I observed.
The AutoDetect service is hosted on an Azure instance in the East coast, and therefore utilizes a public IP address within a much larger block of Azure IP addresses. The problem is that sometime in mid October 2024, Fortinet added many of these IPs to their Malicious-Malicious.Server address list. Adding VPS host public IPs to bad IP lists is quite common these days because anyone can pay for a public VPS and start using it for nefarious purposes. Azure is no exception. Unfortunately the specific IP address used by AutoDetect got wrapped up in the block of bad neighbor IPs.
Once I created a firewall exception for the AutoDetect IP, the app redirected to Modern Auth within seconds.
It would be nice if the Azure team did a better job of keeping bad actors out to ensure their IP block don't get blocked for the legitimate services. Or if the Outlook Mobile team hosted the AutoDetect service under a block of IPs not shared with other VPS customers. That would save everyone a lot of trouble.