can you check the below please my friend .
Step 1 In Cisco Unity Connection Administration, expand System Settings > SMTP Configuration, then
select Smart Host.
Step 2 On the Smart Host page, in the Smart Host field, enter the IP address or fully qualified domain name of
the SMTP smart host server. (Enter the fully qualified domain name of the server only if DNS is
configured.)
Step 3 Click on Save.
Step 4 In Cisco Unity Connection Administration, expand System Settings, then select General
Configuration.
Step 5 On the General Configuration page, in the When a recipient cannot be found list, select Relay message
to smart host.
Step 6 Click on Save.
Step 7 In Cisco Unity Connection Administration, expand Users > Message Actions. Select the Accept the
message option from the Voicemail drop- down list not accept and relay. Enter an SMTP Proxy Address for the relay address
field.
go to Tools > Service
Management, and confirm that the service status for the following services is Started:
Connection Mailbox Sync (in the Critical Services section) and restart if it is starting.
I need you to test again with the below
Step 1 In Cisco Unity Connection Administration, expand Tools, then select Task Management.
Step 2 On the Task Definitions page, select Check System Configuration.
Step 3 Select Run Now.
Step 4 Select Refresh to display links to the latest results.
Step 5 Review the results, resolve problems, if any, and re-run the Check System Configuration task until no
more problems .
Other issue , please make sure for the authentication mode which is used ,make sure that is the same on your exchange. If your exchange .Proxy Server is an optional field that allows you to route the traffic using a Proxy server when the Office 365 network is not accessible from Connection.Proxy server .
Users > Unified Messaging Accounts page
type addres of the proxy:Hostname:Port format
please also chech test button on the unified messaging service & check the test buuto (unified messaging accounts).
