I cut the start menu out completely and replaced it with Keypirinha. Instant fuzzy search with no shady web requests, just like on Linux with xfce4-whiskermenu/rofi.

The script looks something like this. It's written from memory and I don't have a Windows machine nearby to test it, but it's better than nothing.

    $path = %windir%\systemapps\microsoft.windows.startmenuexperiencehost*
    get-process *startmenuexperiencehost* | stop-process -force
    takeown /f $path /r /d y
    icacls $path /grant "${env:UserName}:F" /inheritance:d /t /c
    rm -recursive -force $path