There are not multiple sessions between normal ASP.NET page loads, postbacks, and ASP.NET AJAX partial postbacks. I can tell you that with certainty.
Rather than storing the search string in the session, how about just using the search TextBox's contents directly? I can't think of any reason why you'd need to shuffle it around, since it will be available throughout the entire page lifecycle anyway.
Finally, concerning your requirements... Using an UpdatePanel does not fulfill the requirement that your users should be able to use other functionality on the page if that functionality also raises partial postbacks. Only one partial postback can be in progress at a time. If another event is raised while your search is in progress, the search request will be canceled without any notification.
Using a page method or web service for the search would be a much faster, easier, and more robust way of doing it. I don't usually plug my own site, but I think a couple of my posts are exactly relevant to what you're doing:
You could use a user control to render the search results through a web service (very much faster than an UpdatePanel): http://encosia.com/2008/02/05/boost-aspnet-performance-with-deferred-content-loading/
Or, you could return the search results as JSON and render that on the client side (even faster): http://encosia.com/2008/06/26/use-jquery-and-aspnet-ajax-to-build-a-client-side-repeater/
Either of those methods could take your search functionality out of the partial postback paradigm, so that it runs faster, uses less bandwidth and server resource, and doesn't preclude other UpdatePanel activity from occurring concurrently.