@Michael ... hmm, odd. We did see exactly that problem ourselves-- Outlook selecting IMAP instead of MAPI when we were using hostnames with 'mx' instead of 'mail'. Example: 'mx1.domain.com' instead of 'mail.domain.com'.
Kyle in ST support said to change the 'mx' FQDNs to 'mail' and we resisted, because we'd been doing it that way for over 20 years. But, once we followed his advice, all of our autodiscover problems stopped. He said Microsoft is a lot more intolerant of non-'mail' hostnames now than previously. So, even if you are confident in your setup, it might be worth doing one last end-to-end check. (also make sure MAPI is actually enabled for the domain and the user accounts themselves)
Note that you do NOT have to change the actual name of the server. Just start using 'mail.domain.com' in your DNS A records, autodiscover records, and in the "Hostname" field in each domain's Configuration tab.
It sounds crazy, but as soon as we made that simple change (thanks, Kyle) Outlook started connecting with MAPI by default.