Q:

Is quadratic programming still NP-hard if you have bounds and a feasible point?

The reason I am wondering this is that all of the reductions from 3-SAT => quadratic programming (or similar NP-hard reductions) involve encoding the underlying NP-hard problem into feasibility testing.  If you take out that trick, can you still find another way to encode it?
EDIT:  Killed the duality stuff, don't know what I was thinking.

A:

No; I think what you're observing is a side effect of reducing from deicision problems; if you tried to encode an NP optimization problem, you'd end up using more than just the feasibility machinery.
Take MAX-CUT, with variables $x_i\in\{-1,+1\}$ indicating taking a vertex or not, and
$W\in\mathbb{R}^{n\times n}$ a matrix of edge weights.  Since cut capacity can be written as $\frac 1 2\sum_{i<j} W_{ij}(1-x_ix_j)$, the optimization problem has form
$$
\min\  x^TWx \quad\quad \textrm{subject to} \quad \forall i\centerdot x_i^2 = 1.
$$
Even the real-valued relaxation $x_i\in [-1,+1]$ is problematic since $W$ is in general indefinite.  Like I said above, since we're trying to solve an NP optimization problem, we are definitely relying on the optimization machinery.
As a final point, I'm not sure why you brought duality into the picture, since the usual guarantees of strong duality are murky once nonconvexity enters the picture ....

