I have disallowed SearchUI.exe on one system and renamed SearchUI in another install, both ways seem to make the start menu way quicker.
The Windows search has imo been crap (practically non-working state) since Vista, and so I don't use it... I have my most commonly used shortcuts pinned to the taskbar and do not miss the [WinKey] + 'start typing' feature at all as I mostly use [WinKey]+[R]+'type name of executable'. In the event I need to start the more seldom used programs, I can navigate a working start menu..
This is my current complete key for those wanting it, snapped out of Windows 10 Enterprise edition 1511
Windows Registry Editor Version 5.00
'ConnectedSearchSafeSearch' is filtering which comes into play if search is on and 3 means do not filter results. The rest sould be pretty self-explanatory.
Personally, I have the Windows search service disabled as well as Cortana and do not allow indexing of my drives as I need a working search, not one wasting more of my time searching a single folder than for example the freeware Everything spend indexing my entire system..