What is known about learning a maximal independent set in a (very) sparse graph?
Roughly $O(k \log(n/k))$ queries suffice, in the regime you are talking about.

We can equivalently think of this as finding a minimal vertex cover for $G$, given ability to query whether a particular set is a vertex cover or not.  The  algorithm is as follows:


Let $S := V$ (the set of all vertices).
While $S$ is not a minimal vertex cover:


Pick a random subset $T \subseteq S$ of size $|T| = \lceil |S|/k \rceil$.
If $S \setminus T$ is a vertex cover, let $S := S \setminus T$.



Note that the final vertex cover will have size $\le k$.

How many iterations does this take to converge?  Well, for $S \setminus T$ to be a vertex cover, $T$ must avoid all of the vertices in the final minimal vertex cover, so the probability that a $S \setminus T$ is a vertex cover is at least

$$\left(1 - {k \over |S|}\right)^{|T|} \approx \left(1 - {k \over |S|}\right)^{|S|/k} \approx 1/e.$$

In other words, there is a constant probability in each iteration that $S \setminus T$ is a vertex cover.  Thus, the total number of iterations is proportional to the number of times that we succeed in reducing the size of $S$.

Each time that we successfully reduce the size of $S$, we multiply its size by a factor of $1 - 1/k$.  We start with $n$ vertices, and end with about $k$ vertices, so the number of reductions $r$ satisfies

$$n \times \left(1 - {1 \over k}\right)^r = k,$$

or in other words,

$$r = {\log(k/n) \over \log(1 - 1/k)} \approx k \log(k/n).$$

Thus, we do a total of $O(k \log(k/n))$ iterations, i.e., a total of $O(k \log(k/n))$ queries.  When the algorithm terminates, we have found a minimal vertex cover.

What is the cost of testing the termination condition?  The algorithm terminates when we have already tried all possible subsets $T$ of $S$ and none of them can be removed from $S$ ($S \setminus T$ was not a vertex cover for any subset $T$ of size $\lceil |S|/k \rceil$).  Note that we'll end with a vertex cover of size $\le k$, so in the last iterations, $|T|=1$, so it'll only take $O(k \log k)$ iterations before we've tried all possibilities for $T$.  At that point the procedure terminates.  So, this doesn't increase the total asymptotic running time.

You can think of this algorithm as a simple variant of delta debugging.