I finally found the answer to the broken Start menu search in Windows 11. Bing Search cannot be disabled. We used Group Policy to disable Bing Search via User Configuration\Preferences\Windows Settings\Registry. The registry key was HKEY_CURRENT_USER\SOFTWARE\Microsoft\Windows\CurrentVersion\Search -ValueName BingSearchEnabled -ValueType REG_DWORD -ValueData 0x0
I first tested the delinking of the policy (a test GPO with just this one entry). This removed the registry from HKCU, but the entries stayed in all users' registry SIDs of HKU down the same path. I then edited the GPO, right-clicked on the registry entry named BingSearchEnabled > Properties > selected the Common tab > and selected 'Remove this item when no longer applied', which also changes the action from Update to Replace. I ran a gpupdate on the test system and rebooted. After logging in, ran gpresult and confirmed that the GPO changed the registry entry to Replace mode instead of Update. I went back to GPMC and delinked the GPO > ran gpupdate /force /boot on test machine > tested the Start menu search and it worked > ran gpresult ensuring the registry entry was removed > and finally confirmed the changes in the registry.
If doing this through GPMC, this will be a two step process. The registry entry properties must be changed to 'Remove this item when it is no longer applied' which also changes the Action to replace. You will need to give your system time to replicate that out to all systems and users. This could take weeks depending on size and how many employees you have and how many are out of the office, et cetera. Once you feel comfortable about the propagation, then the entry can be deleted. Even then, there will probably be clean up left over.
The fastest fix is to change the entry from 0x0 to 0x1. This will still take time to propagate and will not apply until users log off of the system and then log back in. Down the road, this registry entry can be removed altogether because the above proves the default is to have Bing search enabled.
There are other settings to manage cloud search. Computer Configuration\Policies\Administrative Templates\Windows Components\Search and User Configurations\Policies\Administrative Templates\Windows Components\Search.
Best of luck, Justin.