If there are equal coefficients for $x^{2n-t}$ and $x^t$ for all $0 \le t \lt n$ then we have $n+1$ unknown coefficients so $n+1$ points suffice. Of course that is still $O(n).$ Then the top c oeffcient is $y(0)$ but that is no fun. I'll focus on the middle coefficient.

 - For the quadratic case $y=ax^2+bx+a$ we have $y(i)=bi.$ 

 - For $y=ax^4+bx^3+cx^2+bx+a$ we have $y(I)=2a+c$ and $y(0)=a.$

 - for $y=ax^6+bx^5+cx^4+dx^3+cx^2+bx+a$ it is enough to have $y$ at $i$ and at $\frac{\pm1+\sqrt{3}i}{2}$ 

This suggests a reduction from  $n+1$ to $n$ points. This is not using the fact that the coefficients are integers.

For the case $2n=4$ there the values $u=\sqrt{-2+\sqrt{-5}},v=-\sqrt{-2-\sqrt{-5}}$ make $v^4+1=-(u^4+1)$, $v^3+v=-(u^3+u)$ but $v^2 \ne -u^2$ thus one can find $c$ along with a certain linear combination of $a,b$ but not $a$ or $b.$ 

A useful question might be "we have a polynomial of degree $2n$ with (symmetric) integer coefficients. How many function evaluations are needed to decide if the middle coefficient is $0$ or not?"

I don't know if you consider complex inputs reasonable. I imagine one might be able to use an appropriate finite field instead. 

It sounds as if another question is something like: " Suppose that $a_1,a_2,\cdots,a_k$ are values such that $f(a_i)=0$ where $f$ has degree $2n$. What conditions on $n,k$ the coefficients and the $a_i$ are such that $f$ is forced to be the zero polynomial (or to have degree a certain coefficient be zero)" The conditions might be bounds on the size. This is related to the question of how few evaluations determine the coefficient(s) without regard to how much work it is to extract them.