This was definitely how it worked until around this time last year.
Somebody has already stated which update that broke it, but by the time I found this thread, the option to remove the offending update had been removed.
My workflow involves me switching between thousands of directories, usually centring on a dozen or so over a period of a few weeks until a project has finished. Having to search the entire system over and over and over is extremely time-consuming!
Prior to this, all recent directories and files appeared the moment I clicked in the search box.
I just spent several hours testing old Windows 11 builds, starting with 22H2 build 382 from September 2022 and then builds 900, 963, 1105, 1265, and finally 1413 (KB5023706) from March 2023.
All of the builds, prior to 1413, provided a history drop-down list in the Explorer search box. All of those builds also required pressing Enter in the Explorer search box. None of them displayed results as you type in the Search box.
Starting with build 1413, the Search box behavior changed to show results as you type. Also, at this point, the history drop-down list no longer existed.
Based on my test observations, there was never a point where the Search box in Windows 11 displayed results as you type AND provided a history drop-down list.
As I mentioned earlier, it would have been relatively easy for Microsoft to provide a check box to let you select the old or new behavior. That would have been the appropriate, customer-oriented thing to do.
There may have been some other reason behind the change, such as the Bing decoupling required by the EU, and maybe they just reverted to the old search code rather than programming something new. It's hard to get any good information about why/how Microsoft changes/breaks things in Explorer because there's absolutely no transparency when it comes to those UI/UX changes. Microsoft has the terrible habit of bundling Explorer changes with "Security updates" with zero information about the UI/UX changes in the release notes. If they actually documented these changes I wouldn't have had to do all that trial and error testing.