Agreed, There is a lot of bad information on this thread, but I don't think you have the final solution either. I suspected certs were a possible reason and installed our self signed certs via Certificate Manager before I ever
posted. Still no luck.
Regardless, the fact of the matter is the mail app doesn't connect where other devices can without problem. You could argue that the added security you speak of is a "feature" but to the end user, it's a bug. Other manufacturer's device and OS products
are considered secure by our IT standards and they either do not have this requirement or handle it automatically. They connect, my surface does not... And I hope Microsoft does not consider the downloading and installation of certificates as a solution.
At best, it should be a work-around until, like every other device I own, it just works out of the box.
But like I said, this didn't work for me. I even used OpenSSL to retrieve the entire certificate chain to be sure I wasn't missing something from IE. I was by the Microsoft Store last weekend and as a shot in the dark asked if they had heard anything
about connecting to mail being an issue. They told me that they had many
users who were experiencing the problem and were quite frustrated. Some were even connecting to Office 365 mail; Microsoft's own exchange servers!
I do appreciate you bringing some clarity on domains and compatibility. Well Done.
Did you install the cert to the correct location? If you just let the manager install the cert to its default location it will not work.