Is the query dynamic or static. If the query is static you could increase the speed of the query by writing the query in Access. If your query is dynamic you will more than likely need to build it in your VB
Also, it has generally been my experience a query that takes that long to run, in the scenario you described, is returning too much data. You could create a query that limits the amount of data returned.
I think you probably have several options available but I would need some more information.
At the risk of sounding ignorant what do you mean by "9 Lacs of records"?