I know it has been a long time since you posted this question, but thought I would let you know how we have dealt with this problem as it may still help you or somebody else.
We have disabled the search function using AppLocker and then placed shortcuts to commonly used applications (E.g. Office) on the desktop. We have also deployed a Start Menu layout which contains tiles for all of the common applications so Word, Excel etc all have a tile on the Start Menu. I know you didn't want to completely disable the search function, but maybe the Start Menu layout and desktop could be an acceptable compromise?
To configure AppLocker to block the search function I created the following rule:
Note: For those who have never used AppLocker, it can be found here
COMPUTER Configuration\Policies\Windows Settings\Security Settings\Application Control Policies\AppLocker
Under Packaged app Rules
I created a policy with the following settings. I chose to Allow all packages by default and create exceptions for anything I wanted to disable. You could just configure a Deny rule for the Cortana package instead.
Action: Allow
User: Everyone
Publisher: *
Package name: *
Package version: 0.0.0.0 And above
Exceptions:
Publisher: CN=Microsoft Windows, O=Microsoft Corporation, L=Redmond, S=Washington, C=US
Package name: Microsoft.Windows.Cortana
Package version: * And above
I then created another rule which allowed all packages with no exceptions and applied it to a security group which contains myself and my colleges (E.g. DOMAIN\IT Support) to stop it from preventing us access to everything my first rule blocks. (NOTE: I found that using the Administrators group didn't work well for this as you would need to elevate your account/run as administrator to use anything which was blocked. Using another group such as 'IT Support Staff' works much better).
To deploy the Star Menu layout I enabled the following policy:
USER Configuration\Policies\Administrative Templates\Start Menu and Taskbar\Start Layout File
I stored the layout file in an accessible share and pointed the policy at that. Here is an example of the layout file:
<LayoutModificationTemplate Version="1" xmlns="http://schemas.microsoft.com/Start/2014/LayoutModification">
<LayoutOptions StartTileGroupCellWidth="6" />
<DefaultLayoutOverride>
<StartLayoutCollection>
<defaultlayout:StartLayout GroupCellWidth="6" xmlns:defaultlayout="http://schemas.microsoft.com/Start/2014/FullDefaultLayout">
<start:Group Name="Internet" xmlns:start="http://schemas.microsoft.com/Start/2014/StartLayout">
<start:DesktopApplicationTile Size="2x2" Column="0" Row="0" DesktopApplicationID="Microsoft.Windows.Computer" />
<start:DesktopApplicationTile Size="2x2" Column="2" Row="0" DesktopApplicationLinkPath="%ALLUSERSPROFILE%\Microsoft\Windows\Start Menu\Programs\Internet Explorer.lnk" />
<start:DesktopApplicationTile Size="2x2" Column="4" Row="0" DesktopApplicationID="Chrome" />
<start:DesktopApplicationTile Size="2x2" Column="0" Row="2" DesktopApplicationID="N:\" />
</start:Group>
<start:Group Name="Office" xmlns:start="http://schemas.microsoft.com/Start/2014/StartLayout">
<start:DesktopApplicationTile Size="2x2" Column="0" Row="2" DesktopApplicationID="{6D809377-6AF0-444B-8957-A3773F02200E}\Microsoft Office\Office16\MSACCESS.EXE" />
<start:DesktopApplicationTile Size="2x2" Column="4" Row="2" DesktopApplicationID="{6D809377-6AF0-444B-8957-A3773F02200E}\Microsoft Office\Office16\ONENOTE.EXE" />
<start:DesktopApplicationTile Size="2x2" Column="2" Row="0" DesktopApplicationID="{6D809377-6AF0-444B-8957-A3773F02200E}\Microsoft Office\Office16\EXCEL.EXE" />
<start:DesktopApplicationTile Size="2x2" Column="0" Row="0" DesktopApplicationID="{6D809377-6AF0-444B-8957-A3773F02200E}\Microsoft Office\Office16\WINWORD.EXE" />
<start:DesktopApplicationTile Size="2x2" Column="4" Row="0" DesktopApplicationID="{6D809377-6AF0-444B-8957-A3773F02200E}\Microsoft Office\Office16\POWERPNT.EXE" />
<start:DesktopApplicationTile Size="2x2" Column="2" Row="2" DesktopApplicationID="{6D809377-6AF0-444B-8957-A3773F02200E}\Microsoft Office\Office16\MSPUB.EXE" />
<start:Tile Size="2x2" Column="0" Row="4" AppUserModelID="Microsoft.Office.Sway_8wekyb3d8bbwe!Microsoft.Sway" />
<start:DesktopApplicationTile Size="2x2" Column="2" Row="4" DesktopApplicationID="{7C5A40EF-A0FB-4BFC-874A-C0F2E0B9FA8E}\Adobe\Acrobat 9.0\Acrobat\Acrobat.exe" />
</start:Group>
</defaultlayout:StartLayout>
</StartLayoutCollection>
</DefaultLayoutOverride>
</LayoutModificationTemplate>
You can create your own Start Menu layout file by exporting the layout from your own Start Menu. This can be done using this powershell command:
Export-StartLayout –path <path><file name>.xml
More info here: Customize and export Start layout (docs.microsoft.com)
Hope this helps somebody.