What about simply computing the projection of $w$ along the complement of $V$? $$ \tilde w = [I - V(VV^T)^{-1}V^T]w, $$ where $V$ is the matrix that has the basis vectors of $V$ as columns. This $\tilde w$ has all the properties that you look for.

If you are in the non standard scalar product, then there is a symmetric positive matrix $M$ that induces this scalar product. In this case the projection reads $$ \tilde w = [I - V(V^TMV)^{-1}V^TM]w. $$

It is OK, if the scalar product is a black box. You only need it's realization.

What about simply computing the projection of $w$ along the complement of $V$? $$ \tilde w = [I - V(VV^T)^{-1}V^T]w, $$ where $V$ is the matrix that has the basis vectors of $V$ as columns. This $\tilde w$ has all the properties that you look for.

If you are in the non standard scalar product, then there is a symmetric positive matrix $M$ that induces this scalar product. In this case the projection reads $$ \tilde w = [I - V(V^TMV)^{-1}V^TM]w. $$

It is OK, if the scalar product is a black box. You only need it's realization.

EDIT: The costs are mainly in the solve with $(V^TMV)$. If CG is applied, there will be a number of scalar product evaluations needed that scales with $n^2$: $\mathcal O(n)$ evaluations times $\mathcal O(n)$ iterations. (read the comments)