The problem is that you're assuming that the postulates of quantum mechanics automatically assign systems a full position representation... whereas some systems (like a particle with spin) do not have such a representation.
The solution, then, is to look carefully at the postulates of quantum mechanics. There are a bunch of abstract ones - states are rays in Hilbert space, observables are hermitian operators, existence of a hamiltonian, normal unitary evolution under it, probabilities are expectation values, what happens with measurements, and so on - but none of those tell you which Hilbert space to use for which physical system, or what hermitian operators to use for your particular physical observables.
For that, you first need a lot of physical intuition, and you follow a general recipe which goes more or less as
If the system has a classical representation which includes a canonical symplectic structure with position and momentum coordinates defined on the whole real line, and a Poisson bracket which satisfies $\{x,p\}=1$, then assign a Hilbert space tensor factor of $L_2(\mathbb R)$ to each space dimension with position as the $x$ operator and momentum as such and such a derivative.
and which is known as canonical quantization.
Note an important caveat in this recipe: it requires position to be defined on an unbounded interval. Because of von Neumann's representation theorem, postulating the canonical commutation relations $[x,p]=i\hbar$ automatically requires the spectrum of both to be $(-\infty,\infty)$.
This is a very tricky point, and even Dirac stumbled with it: he proposed a quantum theory for the phase of a harmonic oscillator (The quantum theory of the emission and absorption of radiation. P.A.M. Dirac. Proc. R. Soc. Lond. A 114 no. 767, pp. 243–65 (1927)) which eventually proved to be fundamentally flawed. (A good source for why is probably R. Lynch, Phys. Rep. 256, 367 (1995), but Elsevier seems to be down at the moment.)
The bottom line of this is that you need to look at your classical system before you decide how you're going to quantize it. For a particle in an infinite well, does the classical system include the positions outside the well? If so, what's the potential there? It must be "very large", because "infinite" is not a valid value of an operator (i.e. $\hat V|x\rangle=\infty|x\rangle \notin \mathcal H$)... and then you're back in a finite well.
If your classical system does not include positions outside that box, then you need to be careful with what you want your quantum system to be. You definitely can't ask your quantum system to do more than your classical one, so position states outside the box should not form part of your Hilbert space. In one strike, this fixes your problem: energy eigenstates will span all of Hilbert space.
You still need to decide what operators you need to use for momentum and energy, and physical intuition usually serves well there. However, if you want to know exactly why we do things like we do, then you should be looking at the classical system for guidance as to how to quantize. As it happens, the classical system is not completely trouble-free, and any troubles you have quantizing you might have seen coming just from looking at the classical system! For an interesting take on this, I recommend the paper
Classical symptoms of quantum illnesses. Chengjun Zhu and John R. Klauder. Am. J. Phys. 61 no. 7, p. 605 (1993).
This includes a discussion, at the end of section III, of precisely this problem.