Since no one else has taken a stab at this for 2 hours, I'll throw my hat in the ring with a solution that does not rely on viewstate at all (or the ASP.NET model of postbacks).
What if you grabbed all the input values with jQuery and instead of doing a post-back did a post against the page (or a new results.aspx page)? Or, you could make the entire thing asyncrhonous and do an Ajax request against a web method, get fed the results, and populate on the client side as needed?
The unfortunate thing here is you have to reconstruct which type of controls were used to figure construct your search query since that data wont be passed with the viewstate. But I imagine you were already going to have to do some kind of translation of your input data into a query form anyway.
Read here for more information about using jQuery to hit an ASP.NET page method. Remember - page methods must be static (it's an easy oversight).
I'm not sure what you're doing server side to construct your query - but I would highly recommend LINQ. I did a similar "advanced search" function previously, and after a few different attempts found that LINQ was a wonderful tool for this problem, regardless of whether I was hitting SQL with LINQtoSQL or just hitting an in-memory collection of objects.
This worked so well because 1) LINQ is deferred execution and 2) A LINQ query returns another queryable object. The implication here is that you can chain your LINQ queries together as you construct them from your input, instead of having to do a single massive clause translation to SQL or whatever backstore you are using (one of my attempts was constructing SQL clauses with strings, but still passing input data via SQLParameters for SQL injection protection - it was messy and complicated when hand crafted LINQ was orders of magnitude easier to understand and implement).
For example:
List<string> data; // or perhaps your a DB Context for LINQtoSQL?
var query = data.Where(item => item.contains("foo"));
if( {user supplies length search option} )
query = query.Where(item => item.Length < 5);
// etc, etc.
// LINQ doesn't do anything until the query is iterated, at which point
// it will construct the SQL statement without you worrying about details or parameter binding
foreach(string value in query)
; // do something with the results
Because of deferred execution and the queryable return type, you can concatenate LINQ queries to this expression all day long and let it worry about the implementation details (such as converting to a SQL query) at execution time.