A lot of head scratching went on with this issue so thought I'd share for the benefit of others.
I had one user complain that they had sent an email and the receiver went to reply and the address error-ed out. The receiver forwarded me the message and the sender address was in the following format
outlook_<random 16 character alphanumeric>@outlook.com
This was particularly weird as we have our own on premise Exchange Server and don't use Office365 or Outlook.com
The sent message was in the users sent messages in their exchange mailbox, but the message wasn't in the Exchange tracking logs.
It turns out that Microsoft has recently created mailboxes for personal Microsoft Account holders and Outlook 2016's implementation of Autodiscover has a failing where it it tries Office 365 before SCP or any other methods. As the users logon details were the same for their Exchange Mailbox as their Microsoft Account (yes I know, I know....), they were prompted at some stage for their password, which they duly entered and Voila! Autodiscover starting sending some outgoing messages (internal and external addresses) via Outlook.com while still retaining and using the Exchange mailbox for storage. Other messages were delivered normally as usual.
Anyway - thank to a handy Reddit post this Autodiscover "feature" can be disabled.
The fix is to create the following Registry key on affected machine:
Navigate to HKEY_CURRENT_USER\Software\Microsoft\Office\x.0\Outlook\AutoDiscover (x.0 corresponds to the Outlook version: 16.0 = Outlook 2016)
For Outlook 2016 version 16.0.6741.2017 and later versions, please add the following
DWORD: ExcludeExplicitO365Endpoint
value 1
Hope this helps someone..
References below
https://www.reddit.com/r/sysadmin/comments/7pk33j/outlook_2016_password_prompt/
https://support.microsoft.com/en-gb/help/3211279/outlook-2016-implementation-of-autodiscover