have you referred to the following document; http://www.cisco.com/c/en/us/td/docs/voice_ip_comm/connection/9x/unified_messaging/guide/9xcucumgx/9xcucumg025.html#wp1262190
this is what is mentioned for connection communication with O365;
Decide whether you want Connection to be able to search for and communicate with different Office 365 server, or you want Connection to communicate with a specific Office 365 server in case the hostname or the IP Address of the specific Office 365 server is known. Auto Discovery is the recommended option.
If Connection is not already configured to use DNS, use the following CLI commands to configure DNS:
–set network dns
–set network dns options
We recommend that you configure Connection to use the same DNS environment in which the Active Directory environment is publishing its records.
Please rate if this helps.