You need to be careful with the word span. A mathematician will say that the span of a set of vectors is the set of finite linear combinations, so you can only add linear combinations of finitely many at a time to get something in the span. So there are sets that are mutually orthogonal and all normalized but not enough to span the space with finite linear combinations. But we call them complete if the span is large enough so that its completion (by filling in any holes) is the whole space. So in a sense we call an orthonormal set of vectors complete if the infinite linear combinations make up the whole space.
But for infinite linear combinations we need a metric, like that from an inner product. So the whole notion doesn't make sense in an arbitrary vector space but can make sense in a Hilbert Space. In a Hilbert Space not only is there an inner product (and hence a metric) so that we cab talk about the limit, but Cauchy sequences have things to converge to, so there is something to be the limit of your sum.
So when you say complete for an orthonormal basis you are talking about infinite sums. And saying that the sun if the projections is the identity is usually how you express it, but that requires limits of operators not just vectors, so technically you then need to put a metric on your space of operators if you want to characterize it that way, so then completeness of an orthonormal basis now depends on how you define distances and take limits of operators. But you do need to define that if you want to talk about the exponential of an operator.
And as long as we've brought up completeness and operators. I should warn you that when a mathematician says state, as in quantum state, they might mean an operator such as a density operator.
Now this is a matter of terminology, but the word complete is usually reserved as a matter of definition to orthonormal seta of vectors. And as a definition there is nothing deep about it.
If you always think of complete as enough then you are fine. When you have a set of orthonormal vectors so large that you can't add another orthonormal vector then it is complete. When you've filled in so many holes that every Cauchy sequence now has something to converge to then your space is complete.
But that complete set of orthonormal vectors is not as big as it can be if you give up on being orthonormal. As a set if linearly independent vectors there are potentially more vectors that could be added to the set that can't be written as finite linear combinations of the vectors already there. So they are not enough in an algebraic sense it is only in the metric sense that they are enough. And that's morally why you insist on orthogonality, it is only when you insisted on orthogonality that you had a sense where you couldn't add more.
Oh, and a basis is supposed to just barely span, so not have too many. The coherent states from another answer are overcomplete and have too many vectors.