IMAPISession::OpenMsgStore() returns MAPI_E_VERSION (0x80040110)

As documented previously, Exchange 2016 will not allow connections from Exchange's MAPI (aka MAPI \ CDO).  MAPI client applications may receive the error MAPI_E_VERSION (0x80040110).  If you are running On-Premises Exchange 2016 and have access to the RPC Client Access logs, you will see this error in the log around the time that the connection was attempted:

RpcDispatch: [RpcServerException] Client version 6.0.XXXX.0 is below the minimum required version 10.0.0.0. (StoreError=Version)

The recommended approach is to use Exchange Web Services or the REST APIs to access the Exchange mailbox.  As a temporary workaround you could try porting the MAPI client application to Outlook's MAPI, but Outlook's MAPI can't log into Recovery Databases and have other nuances that may make this not viable.