If you've got a web application with long running queries, check out Brad McCabe's article from asp.netPRO: Make a Progress Indicator For Slow-Loading Pages. It's a simple method to display something meaningful to the user, but still allows the server to perform the lengthy process. I've seen other variations on this, but Brad's is direct and easy to follow
Of course, I'd also make sure to use Stored Procedures to optimize query performance. Caching, too, could play a role here (imagine customers duplicating the same search request!). Check out the Caching Architecture Guide from Microsoft (Darrell Norton turned me on to this series a long time ago) for details, and I'd also suggest the Caching Application Block.
If you're really adventurous (some would say foolish), you could asynchronously perform the search and notify the user when it's complete. This is, indeed, trickier, and warrants a few posts in their own right. Maybe this weekend . . .
Happy .Netting!