MBorofsky,
I have a routine that checks a list of tables for at least 1 row. It's a little different because you may have joins that slow the return significantly, but what I did is wrote a set of queries that say, "Select Top 1 * from....". These are all linked Oracle tables, some with millions of rows, but my response is blindingly fast.
The "Top 1" thing says when you get a row built, display it and stop looking. Of course, you would not need to display the data, just return the top row into a recordset and check the recordset's EOF property. You could even use the same recordset for all of your queries.
If you took your set of queries and either fiddled Top 1 temporarily into the SQL, or made a copy of the query with Top 1 and ran that, my guess is that you could rip through a list of queries pretty fast.
If you're not familiar with the way to fiddle with a query's underlying SQL, check out the querydefs collection and the querydef object.
Tranman