dangorham
See if there is a policy attached to the user (on the microsoft side) that is restricting IMAP. They have commands you can run for each user to see if it's enabled, etc. You'd need to look at guides online for such steps.
If you are using a hosting company instead of running your own server/vm then I'd recommend reaching out to them to see if they disable external IMAP, etc. I've seen in the past where such restrictions from hosts causes such issues.
Cheers.