I'm afraid I'm going to have to quote quite a bit myself now.
"Let's tell the users everything about this table, and let the user choose." Kind like how Jet handles linked table as a local database object, which AFAIK, are nothing more than a descriptors of what the table looks like and how to connect to that table. When using ADO, that extra information/functionality seems to be missing.
It's true - with a linked ODBC table Access stores a local cache of the table's schema when you link it to save a fetch to the server to determine that. (It's why you need to refresh the link after altering the definition on the server - some consider that a pain - but the performance hit of constantly checking schema information would be worse!)
ADO doesn't offer that as such no - naturally not really as it's an in memory API technology, Access maintains a permanent Jet file presense to hold it's definitions).
However I don't see any reason for a wasteful request of data to ever be required to give users a free choice of the table? All you need is the definition. This could be achieved by either storing that definition somewhere in Access (even a linked table!) or in a local table's data - or establishing the schema via ADO in a once-per-session read of it.
Upon application startup - hit the server, read the schema and return it.
You could do this simply via ADO (using an *empty* recordset) - or in greater depth via ADOX. If you had linked tables still - I'd see little reason not to just look at the definition there.
Once you have the schema you can present options to the users and build efficient data requests upon that.
Access (via Jet) is indeed capable of making iterative (batch) requests for data to load a recordset.
DAO is too - and so is ADO really. It's just that the bringing together of the functionality (binding a recordset to a form) isn't letting you use the formal (asynchronous recordset) method of doing so.
(As VBA is single threaded anyway - there's effort involved in watching the loading of the asynchronous recordset.)
Just allowing ADO's default, on demand, recordset data loading should be pretty reasonable. To that end - I'd certainly recommend you try the OLEDB provider and a server side cursor as everything you describe that you want implies this as a requirement. (I'm not a MySQL user so I can't speak to how effective the providers are - and what functionality they expose to ADO but I know folks who do so it must be decent).
With linked sources in a bound form, I can give a loose query
It depends upon what you mean by a "loose" search.
Is it just that one you've not attempted to predict at all? (i.e. to provide a set of unbound controls, each representing a specific field in which to enter criteria). The alternative to that would indeed be one in which you list the fields available in a combo - and enter values in a free text box alongside that field selection.
I rarely implement such search forms myself - they're great for experienced users but for the non-tech savy they can seem daunting.
But they're pretty standard to set up.
The alternative of having combos populated with a full list of values for a given field would indeed be nightmarish performance-wise and one of the reasons I so hate the default FilterByForm functionality in Access.
(Some users who've seen that and expect the functionality like that in any search form feel under-provided for with a free text search but, quite frankly, they've been operating on a small-fry scale).
This would be analogous to your concerns of
>> "but I was afraid that somehow I'd be providing less functionality to what my users were accustomed with a bound form which could show them so many records available"
Users just have to accept - we're building them a scalable professional application that needs to support multiple users and not drag down their server or network. We do that by implementing efficient and appropriate solutions for them.
Creating a temporary table would, IINM, entail writing/reading to hard drives. Not what I want, not necessarily because of performance, but rather because it just wastes the drives' life
I have to say - that's a new, unique concern to me. I've never been shy about using the local disk - and I never will be. I'll make no apologies to a client for using their client PC hardware to offload server work when appropriate

The local Jet tables we have at our disposal in Access are a massive benefit.
The dataset is small, but I can see users moving through several rows, each having several child records requiring between 3 to 5 subforms.
Now
that's an interesting comment.
The issue you're having is that you have a hierarchy displayed? More than just parent child?
Or is the issue here that you're displaying many parent records to the user - leaving them free to navigate through the resultset at will?
Again - that comes down to selectivity then.
Forcing the user to bring over what they will want. Not browse at leisure through what's there already.
If it can be done totally in memory, e.g. with a recordset, I'm all for it, except I can't think of a good way to link a subform to a recordset.
I don't follow you. You mean other than by direct binding of the recordset as we've been talking about?
There are ways of holding continuous data in a form recordset without having a table to bind to (using a constructed ADO recordset). I wrote an article on it for Access Advisor last year and the accompanying MDB can be found near the bottom of my examples page.
But you still need to fill such disconnected recordsets with
something.
And that data needs to be fetched. You'd likely be as well to stick with a disconnected recordset loaded directly from the source.
I'm still not clear on the overall structure that you're intending on implementing - and so what would be of most benefit.
Obviously with form binding to recordsets - we don't have Access Master/Child link fields for subform convenience...
If you do have a few parent records and each has child records then you could maintain a larger recordset than is currently visible for the child records and filter it appropriately as the parent records are navigated.
like immediately loading first row, but not displaying the total recordcount until either it has loaded everything or the user has moved to the last record.
A form bound to a non clientside cursor recordset will generally display something approaching this type of behaviour - albeit if not as iterative as Access bound to Jet data. (Client-side curors pop that complete could right up at you - they've already loaded the data by the time the form's usable).
But it does come back to the point that we should be waiting for ADO to load a massive resultset. We don't want to be pepparing the server all the time - I'd take little and often over heavy and less frequent if possible.