Hi all,
We have escalated this new search issue to Windows, and they are working on a fix. There is an issue where Windows is throttling search indexing such that it may not keep up with the most recent email indexing. From what we know right now the fix is not imminent so it might still be a couple months for it to release.
If you need to workaround this until the fix is out, use the TEMPORARY WORKAROUND in this article, Outlook Search not showing recent emails after Windows update KB5008212 (microsoft.com). This workaround tells Outlook to use its built-in search. The Outlook built-in search is slower because it indexes manually when you search, but it does work.
In case it could help I posted the registry keys to enable or disable the workaround on OneDrive, https://1drv.ms/u/s!AobSYdEz_BdhhuZZo1KZ0xAi7U7t-w?e=YldLBT.
When I get more information on the fix, I will post back with any status updates.