In Zermelo-Fraenkel set theory without the Axiom of Choice (AC), there exist models in which not all vector spaces have a basis.
Suppose $V$ is a Hilbert space (over the complex numbers), and assume that $V$ does not have a basis.
Then an observable $U$ (Hermitian operator) cannot have an orthogonal eigenbase. It still has some set of orthogonal eigenvectors, but they do not generate the Hilbert space.
What is the quantum-theoretical significance of this phenomenon?
There are (at least) two notions of the basis for a vector space. There is no ambiguity for finite-dimensional spaces, but the notions differ when the dimension is infinite. The definition that is usually preferred by mathematicians (because it allows the straightforward generalization of many theorems for finite-dimensional vector spaces to larger ones) is the "Hamel" or "algebraic" basis. Using a Hamel basis means defining the span of a collection of vectors to consist of all finite linear combinations of basis elements. Consider the the vector space ${\bf R}^{\omega}$, consisting of a Cartesian product of a countable number of copies of the real numbers ${\bf R}$, from this viewpoint. Using addition and scalar multiplication term by term, this is clearly a vector space and generalizes the finite-dimensional real vector spaces ${\bf R}^{n}$. However, in this case countable set of vectors $e_{i}=(0,0,\ldots,0,1,0,\ldots)$, each with a $1$ in the $i$th position, do not form a basis, because $(1,1,1,\ldots)$ is not in the linear span of any finite number of the $e_{i}$. There is, in fact, no countable basis for this vector space, although with the Axiom of Choice, it can be proven that there is a Hamel basis for ${\bf R}^{\omega}$—or, indeed, any vector space. However the basis is very large; the Hamel basis for ${\bf R}^{\omega}$ has cardinality $\mathfrak{c}$, the cardinality of the continuum and thus the same as the cardinality of ${\bf R}^{\omega}$ itself.
However, this is not a useful notion of a basis in physics. In physics, we routinely take infinite linear combinations of basis elements and work with them. The notion of basis that allows for this is the "Schauder" basis. Allowing countably infinite sums complicates matters, since there are possible convergence issues. However, by restricting attention to convergent sums, we often do recover well-behaved vector spaces; in particular, this is the case for Hilbert spaces. It is provable (without the Axiom of Choice) that every separable Hilbert space (that is, every Hilbert space with a countable dense subset) has a Schauder basis. These Hilbert spaces are exactly the $L^{2}$ spaces of square-integrable functions on various underlying spaces; thus they are the spaces for which we can assign probabilities to events. So the Hilbert spaces of possible interest in quantum mechanics always have bases of the type that is needed for doing physics.
