What troubleshooting have you done?

That bit of information would have been nice to have on the original post so we knew what had changed.

Can the SQL server ping the cloud mail server?

Can the SQL server telnet to the cloud mail server on the correct port?

Has the profile been updated to use the new cloud mail server?

Can you send mail from the outlook client on the SQL server via the cloud mail server?

Has the mail account actually been migrated to the cloud server?

Please provide as much information as you can on what you have tried so far to resolve this issue so that we are not repeating steps you have already taken.