The ellipsoid method applies to this problem: once you fix a degree, the space of polynomials threading through your corridor is a convex set. Given any polynomial, if there is a point on the graph which lies outside the corridor then that point provides a linear inequality (i.e. hyperplane) separating your polynomial from your desired convex set. You can test whether such a point exists, and find it if it does, using the theory of Sturm chains (to save time, you could first test a few random points on the graph before jumping to Sturm chains).

This should give a reasonably fast numerical algorithm. It won't work if the set of polynomials that fit has measure zero, or measure below some constant related to your numerical precision. You can also find an exact algorithm by either using Sturm chains cleverly or just falling back on the Tarski–Seidenberg theorem.

**Edit:** Sturm chains are a great tool and deserve to be more widely known. They let you exactly count the number of real roots of a real polynomial in any given interval. In particular, you can use Sturm chains together with binary search to find arbitrarily good approximation to the real roots.

Suppose WLOG that a polynomial $f(x)$ has no double roots, and use the Euclidean algorithm for $\mathbb{R}[x]$ to produce a sequence of polynomials $f_i(x)$ of strictly decreasing degrees with $f_0 = f, f_1 = f'$, and $f_{i-1} + f_{i+1}$ a multiple of $f_i$ for $i \ge 1$, ending with a constant polynomial. For any real number $x$, define $\text{sc}_f(x)$ to be the number of sign changes in the sequence $f_0(x), f_1(x), ...$ (ignoring internal $0$s). Then the number of real roots of $f$ in the half-open interval $(a,b]$ is just $\text{sc}_f(a) - \text{sc}_f(b)$.

(A possible issue here is that when $f$ is very close to having a double root, applying the Euclidean algorithm to $f, f'$ might be numerically unstable.)