Looks like you are doing the complete search with every page retrieval (did I just sound like MS Office Assistant?).
One way you could reduce search time is to do the full search and:
1) Stick the results into a temporary table. Include an expiry just in case results are never looked at.
2) Serialize the results and put them into a session variable. I put this as option 2, because the more I think about it, the stupider this idea becomes. I think there's a very definite size limit which you will almost definitley cross in this situation. But I've left this idea in because it might spring another thought somewhere.
Eitherway, the main search is only being done once. Subsequent pages are retrieved from a much smaller table. If you want to get really cleaver, you could look into doing some form of cacheing in this way, but I suspect this would be a lot more effort than it would be worth.
Sorry, not really any answers in this post, but hope it helps a little.