my answers :
- javascript(do'h wrong place?)
print the beginning of the page with the "Searching" in a DIV element (set an ID for future use), do the actual search and before outputing the results output a javascript hidding the div...
one thing you might concider is that the NS and IE DOM are different so the javascript hidding the div won't be the same.
- Temp table(getting closer)
perform your search in the "Searching ..." page. At the end of search generate a temp table with results (beware of table size though) and set a session variable with temp table name or pass it along as query string, whatever. In search result display page, get temp table's name. display it content and delete it...
- Optimize(my choice)
Optimize your table structure you SQL query and you indexes to speed up the search