We are seeing odd behavior for emails sent to our on-premises Exchange 2013 server.

Mails sent from Outlook.com with at least one invalid address on the To field are bouncing back to the sender as undeliverable to all addresses...even the valid ones, and the valid recipients do not receive the email.  The same mail sent from Gmail does bounce back indicating that it could not be delivered to the recipient and the valid recipient(s) do get the emails.

The SMTP protocol logs for both are below.  Any idea why the behavior would differ?  Note:  This is causing issues for us as emails from Microsoft employees behave the same way.

From what I can see in the logs, it looks like the problem is that Outlook.com is using the same SessionID for both recipients, so when the User unknown goes back it has no way of knowing which recipient was invalid and the mail is rejected for all senders.

I could be wrong, but this seems like a fundamental problem with how Outlook (and as a result...Microsoft as a whole) is sending mails.