I'm guessing your /epi/ui/shell is your virtual path to your EPiServerShell?

Test to see if you can access /epi/ui/shell/Search should take you to the search "page".

Yes I can access the search "page" at  /epi/ui/shell/Search. But not complete any search.

i get this issue when for the first time i press enter in the search i get a page with error ( /cms/shell/search)

when we press the search or press enter it works as usaual ( the ajax style)

This information might be helpful to someone who has the answer in store: 

[HttpException]: A public action method 'Search' could not be found on controller 'EPiServer.Shell.UI.Controllers.SearchController'.   at System.Web.Mvc.Controller.HandleUnknownAction(String actionName)   at System.Web.Mvc.Controller.ExecuteCore()   at System.Web.Mvc.ControllerBase.Execute(RequestContext requestContext)   at System.Web.Mvc.ControllerBase.System.Web.Mvc.IController.Execute(RequestContext requestContext)   at EPiServer.Shell.Web.Mvc.ModuleMvcHandler.ProcessRequest(HttpContextBase httpContext)   at System.Web.Mvc.MvcHandler.ProcessRequest(HttpContext httpContext)   at System.Web.Mvc.MvcHandler.System.Web.IHttpHandler.ProcessRequest(HttpContext httpContext)   at System.Web.HttpApplication.CallHandlerExecutionStep.System.Web.HttpApplication.IExecutionStep.Execute()   at System.Web.HttpApplication.ExecuteStep(IExecutionStep step, Boolean& completedSynchronously)

As a note: Other mvc-related paths work.

got the same problem here,  the first time we search ( after iisreset) we get this error

The search action of the search controller only accepts POST requests, therefore you'll end up with a 404 when trying to do a GET request.
Since the search results are requested using an ajax post, or rather one request for each search provider, and returned as json there's no point in letting the browser do a regular post. It would have been nice if the form had had the action attribute set to post though.

I don't quite understand why you're getting problems on the fist request. Is the request done with ajax, or is the form sent in the "old fashioned" way?

Is it possible that the document isn't fully loaded so the client side scripts aren't properly wired up yet, or do you notice any script errors?

I have the same issue on a client site, started today randomly.

Our issue has been resolved by accident. We don't really know what has solved it. Which is a bit peculiar. The editors didn't need the functionality so we had let the case rest. Until we tried it today out of curiousness. Since the problem appeared the first time the site has been somewhat restructured and has had a new SSL-cert in place. So something we've done since then has solved it. Would have been good to have a solution to share with the rest of you.