Having gone through all the replies the summary for me is as follows.
All setup are on-prem Exchange 2010/2013/2016/2019, I have tested on all 4 version.
I have tested with Outlook 2013/2016/2019 using retail packs that are activated, so again not a login on the machine to install, simply a cut and paste of the key. Search fails
I have noticed different behaviour when using MS Open License products where the search works.
I have already done group policies to mitigate the MS login prompt, although Microsoft have now stopped looking at the GP key, so I have now inserted the second manual key into the registry.
//365 Autodiscover
HKEY_CURRENT_USER\SOFTWARE\Policies\Microsoft\office\16.0\outlook\AutoDiscover
Above is where GP puts it(same dword as below) and the new version of Outlook ignores this and looks at the below
HKEY_CURRENT_USER\Software\Microsoft\Office\16.0\Outlook\AutoDiscover
DWORD: ExcludeExplicitO365Endpoint
Value = 1
If a user group has added their domain for use with Teams, but not integrated the AD, even if they have only added one user, they will get prompted for MS for login, at some point, and to stop this will need above. Their search still seems work.
I have now deleted all my accounts from MSA and set up a new one using a outlook.com account and still the search does not work, unlike mwhalenhtc (even after opening and closing Outlook a number of time and restarting the machine) unless it takes some time to update?
The only other place that my emails existing on MS is in the partner portal and on MS Teams, I think
So I am not sure we are there yet!!
Gabe_Bratton do you want some more traces?