I've very surprised that both Microsoft's and Oracle's ODBC drivers don't support async queries.
I appears that you're stuck submitting the query twice: once with a COUNT(*) and once to return the data.
What about evaluating the type of search the user wants to do and warn them. Any query that has no search criteria or tries to do a 'contains' type search could take a long time to execute. Probably a lot of ORs in the search string could cause longer execution times. Betweens, less than, greater than, and equal type searches should all be optimizable.
-Mike