I just read the wikipedia article on QCQPs, and my impression is that a QCQP can only be NP-hard in the non-convex case. Since you specify that you have a convex QCQP, I believe the problem can be solved in polynomial time with interior point methods.
I could be mistaken though.
I think you may be misunderstanding how the simplex method is used to solve quadratic programs. It doesn't operate on the vertices of the feasible region of the original quadratic program; it operates on the vertices of the feasible region of the KKT conditions for the original quadratic program. This is because 1) the KKT conditions are sufficient as well as necessary for convex problems, and 2) for a quadratic program the KKT conditions are linear (well, except for complementary slackness, but that can be handled easily). Thus solving the original convex quadratic program reduces to solving its linear KKT conditions, and the simplex method is used to handle the latter. (See, for example, here.)
All of this means that the simplex method will output a vertex of the feasible region of the KKT conditions rather than necessarily a vertex of the feasible region of the original quadratic program.
However, if the quadratic program has the optimal solution at a vertex it means that if you use any of the algorithms for linear programming the algorithm will output that vertex as the optimal solution. (Well, assuming there aren't multiple optimal solutions.) So if you use one of the polynomial-time algorithms, that algorithm will output the vertex you want in polynomial time. For example, the ellipsoid method will work just fine, as in this recent answer on Math Overflow.
Added: If the quadratic programming problem has multiple optimal solutions, and you use, say, a polynomial-time interior-point algorithm to find one of them, it won't necessarily find one of the vertex optimal solutions. However, there is a polynomial-time algorithm due to Berkelaar, Jansen, Roos, and Terlaky for finding an optimal basis (which will give you an optimal vertex) from an optimal interior solution to a quadratic program. So all of that together will get you to an optimal vertex in polynomial time.
Best Answer
For feasibility, only the constraints matter, not the objective. One way to identify a feasible point (even if there exist no strictly feasible point), is to solve the feasibility problem $$ \min \ 0 \quad \text{subject to your constraints}. $$ Usually, this is not a much better-behaved problem than the original problem. An alternative is to minimize the infeasibility residual $$ \min \ \|\text{constraints}\|^2 $$ (assuming equality constraints). This is typically a nonlinear least-squares problem. Depending on the form of your constraints it can be solved more or less efficiently. If your original problem was feasible, this last one is a zero-residual least-squares problem and Gauss-Newton should converge quadratically.
That being said, note that many modern methods do not require an initial feasible point. I may be able to be more specific if you give more details on your problem.