I have a similar problem:
1) No "Search Input" or "Search Results" module in the "Add Modules" pop-down "Search Admin" exists
2) I try to search using the search box under different skins, nothing happens, I stay on the same page.
3) I have verified searching is enabled, ran the re-index job (no errors!)
4) When I try to select the "Search Results page" in "Admin/Site Settings/Advanced" I ONLY get "" as an option where the other drop downs allow me to select a page
5) I've verified the files exist in "Desktop Modules/Admin/SearchAdmin & SearchInput & SearchResults"
6) I removed the "Search Results" page, created a new one, populated with the "Content List" module and the ?Tag searching works
SearchResults?Tag=Regional - Provides results if manually entered (Regional is defined in my taxonomy)
7) REALLY WEIRD RESULTS
SearchResults?Search=team - Nothing except General exception in error log
AssemblyVersion:7.2.0
PortalID:0
PortalName:JJVA Portal
UserID:1
UserName:dnnhost
ActiveTabID:39
ActiveTabName:Search Results
RawURL:/main/DesktopModules/internalservices/API/searchService/preview?keywords=regional&culture=en-US
AbsoluteURL:/main/DesktopModules/internalservices/API/searchService/preview
AbsoluteURLReferrer:http://www.jjva.com/main/SearchResult...
UserAgent:Mozilla/5.0 (Windows NT 6.1; WOW64; rv:26.0) Gecko/20100101 Firefox/26.0
DefaultDataProvider:DotNetNuke.Data.SqlDataProvider, DotNetNuke
ExceptionGUID:a9b93c5f-ae01-4fc6-8bab-8aaf612e338f
InnerException:Index was out of range. Must be non-negative and less than the size of the collection. Parameter name: index
FileName:
FileLineNumber:0
FileColumnNumber:0
Method:System.Collections.ArrayList.get_Item
StackTrace:
Message:
System.ArgumentOutOfRangeException: Index was out of range. Must be non-negative and less than the size of the collection.
Parameter name: index
at System.Collections.ArrayList.get_Item(Int32 index)
at DotNetNuke.Web.InternalServices.SearchServiceController.GetSearchModule()
at DotNetNuke.Web.InternalServices.SearchServiceController.GetSearchModuleSettings()
at DotNetNuke.Web.InternalServices.SearchServiceController.Preview(String keywords, String culture, Int32 forceWild, Int32 portal)
at lambda_method(Closure , Object , Object[] )
at System.Web.Http.Controllers.ReflectedHttpActionDescriptor.ActionExecutor.<>c__DisplayClass13.b__c(Object instance, Object[] methodParameters)
at System.Web.Http.Controllers.ReflectedHttpActionDescriptor.ActionExecutor.Execute(Object instance, Object[] arguments)
at System.Web.Http.Controllers.ReflectedHttpActionDescriptor.<>c__DisplayClass5.b__4()
at System.Threading.Tasks.TaskHelpers.RunSynchronously[TResult](Func`1 func, CancellationToken cancellationToken)

Any thoughts?
Thanks!