Implicit Postulate of Quantum Mechanics Consider the following quantum system: a particle in a one dimensional box (= infinite potential well).
The energy eigenstates wave functions all vanish outside the box. But the position eigenstates wave functions don't all vanish outside the box. Each one of them is a delta function at a specific location, and some of these locations are outside the box.
So it seems that there is no overlap between certain position eigenstates and all energy eigenstates. So the energy eigenstates don't span the whole Hilbert space! And these position states have zero probability for any energy outcome in a measurement!
Now, I know that when speaking about an infinite potential well, it is assumed the particle cannot be outside the well. But I don't see any reason to assume this from the postulates of quantum mechanics. Is there an implicit additional postulates that says: "The Hilbert space of the system is spanned by the Hamiltonian operator's eigenstates (and not other operators, such as position)"? Or is the infinite potential well just an ill defined system because it contains infinities (just like free particle...)?
 A: 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.
A: My understanding is that in various problems in quantum mechanics the final step is to restrict the Hilbert space to physically permissible states. In this problem, such a restriction requires that the state is supported exclusively on the spatial interval in which the potential is finite. This would imply the resolution of your paradox is that the position eigenstates outside of this interval are not in the Hilbert space.
This is not the only example of such a restriction. In the harmonic oscillator there is a similar restriction, that we limit our Hilbert space to states which can be eventually annihilated to the vacuum, and we reject those which can be lowered arbitrarily. Similarly when quantising the vector field we find the non-physical degrees of freedom allow for states of zero norm, in order to recover physicality, and a theory which obeys the appropriate gauge conditions, we reject these.
A: This is just a question of choosing a base for the vector (Hilbert) space: The set of position eigenstates is one base, the set of energy eigenstates is another. They can be expressed in terms of each other (vectors/states from base B1 can be expressed as a sum of vectors from base B2).
All in the theory of vector spaces...
OP said: "But the point of my question is that for the particle in the box, a certain position eigenstate (any one which has as it's wave function a Dirac delta outside the box) cannot be expressed in terms of energy eigenstates"
Ah, you're right, now I understand your question. I think the point is, that the well is infinite. For a pfinite potential well, you always have "unbound" higher energy states which can be used to sum up the eigenvectors outside of the box. In the case of infinite well, those states have an energy of infinite (their energy goes to infinite if you let the energy well move to infinity). This way they sort of "vanish" from the model. But: If you accept the same for the position eigenstates (just dripping thos outside the box) everything is OK again: You have "universe" inside a box (a universe where the Koordinate is by design limited to some intervall) and again all position eigenstates can be used to build energy eigenstates and vice versa.
