MicrosoftGabe_Bratton, just wanted to chime in. I've been watching this thread since the issue first popped up. We've had the same issue across multiple clients and our environment is similar to others; Exchange 2016 on-prem. I know for a fact that the primary email address my Outlook is synced to does not match the Office 365 address that Office itself is signed in to. One is mailto:bbaker@domain.comwhile the other is mailto:bbaker@domain.onmicrosoft.com. All of my users are the same way. I do have Microsoft accounts for mailto:bbaker@domain.com,but that's not what is used to sign in to Office and I am fairly confident many users experiencing the search issue DO NOT have any Microsoft account that matches their primary @domain.com email address. Especially since some of the users affected were hired within a week of the bug first showing up so that address never even existed to allow a Microsoft account to be associated with it.
