Patrick,
I tested the current version of Outlook Mobile for Android and was unable to replicate the issue you reported. I tried setting up an account about half a dozen times, deleting the account from Outlook each time. In all those tests, there was one time where the app reported that the account could not be setup because the authentication timed out. Even then, the account was successfully configured in spite of the reported timeout. Diving into SmarterMail's logs seems to indicate that the reported timeout was not on our server, which seems to suggest that the delay was on Microsoft's Servers.
Do you know if your users are seeing this issue on Android or iOS? It is possible that you could be seeing an issue specific to the iOS version of Outlook Mobile. Given the way that Outlook Mobile works, it seems unlikely, but it can't hurt to rule out the possibility.
Andrew Barker
Software Developer
SmarterTools Inc.
www.smartertools.com