I can fetch mail from Office 365 just fine.  It's when I attempt to use the smtp.office365.com relay service, that the SDP hangs and says "Sending notification failed."  Note that if I change this to our on-premise Exchange this works fine.  We're moving to Office 365 though and I need to get this working with it.

From the server that has SDP installed I am able to telnet to smtp.office365.com on port 587.

Here is the output of a powershell attempt to send mail.

PS C:\> send-mailmessage -from servicerequest@mydomain.com -to user@mydomain.com -subject "test email" -body "test smtp rel
ay service" -smtpserver smtp.office365.com -credential $msolcred -usessl -port 587
send-mailmessage : The SMTP server requires a secure connection or the client was not authenticated. The server
response was: 5.7.57 SMTP; Client was not authenticated to send anonymous mail during MAIL FROM
[DM5PR16CA0006.namprd16.prod.outlook.com]
At line:1 char:1
+ send-mailmessage -from servicerequest@mydomain.com -to user@mydomain.com -subject " ...
+ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    + CategoryInfo          : InvalidOperation: (System.Net.Mail.SmtpClient:SmtpClient) [Send-MailMessage], SmtpExcept
   ion
    + FullyQualifiedErrorId : SmtpException,Microsoft.PowerShell.Commands.SendMailMessage