We develop a stability and convergence theory for a class of highly indefinite elliptic boundary value problems (bvps) by considering the Helmholtz equation at high wavenumber k as our model problem. The key element in this theory is a novel k-explicit regularity theory for Helmholtz bvps that is based on decomposing the solution into two parts: the first part has the Sobolev regularity properties expected of second order elliptic PDEs but features k-independent regularity constants; the second part is an analytic function for which k-explicit bounds for all derivatives are given. This decomposition is worked out in detail for several types of bvps, namely, the Helmholtz equation in bounded smooth domains or convex polygonal domains with Robin boundary conditions and in exterior domains with Dirichlet boundary conditions. We present an error analysis for the classical hp-version of the finite element method (hp-FEM) where the dependence on the mesh width h, the approximation order p, and the wavenumber k is given explicitly. In particular, under the assumption that the solution operator for Helmholtz problems is polynomially bounded in k, it is shown that quasi optimality is obtained under the conditions that kh/p is sufficiently small and the polynomial degree p is at least O(logk).