For sure, the example above is in the realizable, exact case which has been solved for decades. The point of our paper is to get similar bounds for the agnostic case. But the prior work for the agnostic case can't even solve the example above.
Hanneke '07
-----
Hanneke '07 fails both algorithmically and analytically on the same example, for $\eta = \epsilon = 3/N$.
You point specifically to Theorem 4 of Hanneke '07, but this has exactly the same issue as Hanneke-Yang '15: the lower bound is for the worst-case distribution over $X$. The relevant line of Theorem 4 of Hanneke '07 is:
$$
XPTD(V,(1-\epsilon)/\epsilon, \delta) \leq \sup_{D' \in \mathcal{D}} LQ(\mathbb{C}, D', \epsilon, \delta, 0)
$$
which involves a supremum over all distributions $D'$ supported on $\mathcal{X}$.
So there *exists* a distribution over the support such that the upper and lower bounds are both related to teaching dimension, but it probably isn't the given distribution. (The bound is also worse in that the lower bound is *partial* teaching dimension, which can be much smaller, particularly if $\delta$ is reasonably large.)
And it's not just an analytical issue, if you read through the Algorithm ReduceAndLabel in Hanneke '07. Consider the same example as above, but with $\eta = \epsilon = \frac{3}{N}$. The optimal algorithm is still $O(\log N)$ queries: just query the last $\lg N$ bits and output that hypothesis, which might be slightly wrong in the unary region but has error $\eta + \frac{2}{N}$.
In Hanneke '07, the first step is to take a sample of $\frac{X}{5 \log |H|}$ examples; in the example above, this is probably going to be entirely in the unary region. Then the algorithm calls Reduce on this sample, which repeatedly takes $O(1/\eta)$-size subsamples and labels their minimal specifying set; but if the original sample is unary, this set will be of size $O(1/\eta)$. So Hanneke '07 will use a linear number of queries on this example.
Wait, you might say, what about Theorem 3 of Hanneke '07? That's an upper bound in terms of extended teaching dimension that doesn't involve a supremum over distributions. But it's analyzing the algorithm that we know fails on this example, so of course it has to be a weak upper bound. Why?
The issue is that the distributional version of extended teaching dimension considered in Hanneke '07 isn't terribly good. It's in terms of a parameter $n$, which is set to about $\frac{1}{16 \eta}$; the distributional extended teaching dimension basically says: if you only had $n$ unlabeled data points from $\mathcal{D}$, how many labels would you need to teach? And in the example, with only $O(N)$ unlabeled data points you will probably still be missing a constant fraction of the binary points, so the teaching dimension remains polynomially high. If you have access to $\gg \frac{1}{\eta}$ unlabeled samples, you can hope to do much better.
[*] It's a minor point, but I think there's an error in the proof of Theorem 3 in Hanneke '07 that slightly affects exactly what polynomial dependence it gets on this example. I think the actual algorithm takes $\tilde{\Omega}(N)$ queries, but the theorem statement would give an $N^{0.99}$ upper bound because you would see a constant fraction of those binary points. The algorithm samples $U_i$ from $U$, then subsamples that *with replacement* and finds a minimal specifying set. The distributional extended teaching dimension bounds the size of the specifying set whp for a *single round* of subsampling, but the double-round subsampling is not exactly the same distribution. The proof of Lemma 3 doesn't do anything to address this issue (it just says "For each, we make at most $t$ label requests with probability $\geq 1 - \frac{\delta}{2s}$", which would be true by assumption for the single round sampling), and in fact on the example with $\eta = \epsilon = 3/N$ it matters a bit. But regardless of whether the bound is $N$ or $N^{0.99}$, it's not the logarithmic dependence of optimal or our algorithm.
On the need for knowing $m^*$
-----
You're right that our algorithm is written to assume $m^\*$, but it's a pretty minor dependence that can be removed. Thanks for pointing it out.
The algorithm only uses $m^\*$ to set the number of iterations $k$ in the first stage. One could modify the algorithm to remove this dependence, as follows: $m^\*$ enters the proof through Lemma 2.1, which combined with (1) gives a lower bound on the expected potential gain in each round. But the quantity being bounded (LHS of Lemma 2.1 / RHS of (1)) does not depend on $h^\*$ or $m^\*$, and can be computed by the algorithm. So the algorithm *knows* a lower bound $\tau_i \gtrsim \frac{1}{m^\*}$ on how much the potential is expected to grow in each round $i$. Then the algorithm can stop as soon as $\sum_{i=1}^k \tau_i \geq O(\log H)$, at which point the potential is positive whp and the second stage will succeed.