This is one of those errors that is a real pain because there are so many issues that can cause it. In this article I wanted to touch on a fairly new issue that causes this issue; MAPI over HTTP.
If you have not heard of MAPI over HTTP, it is the replacement for RPC over HTTP as the default connection method for Exchange 2016. It is also available in 2013 SP1 and later, but not turned on by default. So if you are installing the first Exchange server in an organization and it is Exchange 2016, then MAPI over HTTP is enabled as the default protocol. If the MAPI URL is not configured then Outlook 2013+ clients will see the error above when trying to setup the mailbox.
The fix is pretty easy though. The MAPI virtual directory must be configured to match the certificate name. The below command should do the trick. Just make sure and change the name to the correct one for your environment.
So there you have it. Hopefully this did the trick for you. If you have any questions or suggestions, please leave a comment below.