I am having issues while adding Exchange 2016 (cloud based) to the CIC. CIC Service Account works perfectly fine with manually adding the Exchange Service URL for the authorization (it doesn't work with Autodiscover to fetch Service URL), however if I am trying to add shared mailboxes under "attendant mailboxes", it gives me error while retrieving the mailbox contents with the error - "Failure opening message store: Timeout while communicating with the PostOfficeServer subsystem". Impersonation rights are already in place, not sure if this is something Exchange side or something related to DNS or CIC. Any help on this would be much appreciated.

Were you able to resolve this? This is probably not a fault in CIC and not a timeout getting a response from Post Office, more likely it's a timeout on the search against Exchange. Using EWS the tracing is very clear and readable, so if you turn Post Office to Notes and the Exchange EWS Connector to All, you should be able to find the EwsRequest going to Exchange to search for the mailbox you want to use. Once you find the request, bookmark it and make a note of the thread, then filter on that thread. The first EwsResponse on that thread after the bookmarked request should be the response to that request. If you look at the time gap between them, you'll be able to determine how long it's taking for Exchange to respond, which is probably the issue. You might even find an error on that thread instead of a response, if the request timed out.