I was able to deactivate the module, but not uninstall. I click that option, get the dialog box asking if I want to uninstall, but then module remains, in an inactive state. If I activate it, I still don't have the menu option.
I made those changes, and the 'Search and Indexes' module now shows as Not Installed. Unfortunately, when I click the install option, nothing seems to change - the module remains uninstalled.
Could you please try to open the SystemConfig.config file and remove the version attribute from the Search module line. The line should look like this:
<add name="Search" />