Found cause (I think) of Windows Start Menu taking obnoxiously long (slow, lag) when searching for items

I've submitted this as Windows 11, but it should apply to ANY Windows edition that supports searching the Start Menu using Windows Search / Indexing, so, Windows Vista - Windows 11:

Start search uses Windows Search which uses Indexing Service. By default, MS Indexes %programdata%\Microsoft\Windows\Start Menu - all well and good HOWEVER, by default, MS DOES NOT index %appdata% -- and in there is %appdata%\Microsoft\Windows\Start Menu - and if you check Indexing Options, you will find that no, MS does NOT include that specific directory. I've sent feedback using Feedback Hub on this, but for now, any items in Users' Start Menu folder and not the %programdata% Start Menu folder will cause delays, and it appears Start Menu will wait for those results, so even if your item is in %programdata%, your result will be delayed. NOTE you cannot enable indexing of other users' Start Menu locations unless you FIRST access their profile folder in Explorer to get access (their folders will show as not existing in the Indexing Options dialog as that dialog does not display folders the user does not currently have access to). ALSO, it will take a while for Indexing to update and include results from the users' Start Menu folder, so either find a way to force immediate Indexing, or let the computer idle for a half hour on AC power when testing this.

In summary, to fix this, find Indexing Options in Start, hit Modify, browse to the \Users\{username}\AppData\Microsoft\Windows\Start Menu folder and hit its checkbox, then hit OK, then OK. To fix this for other users on your system, Open Explorer, browse to and select their \Users\{username} folder, click to get access, then repeat the above process to enable Indexing. Then wait for Indexing to update the location(s).