There are at least three notions of basis depending on the mathematical structure you are considering. I will quickly discuss three cases relevant in physics (topological vector spaces are relevant too, but I will not consider them for the shake of brevity).
(1) Pure algebraic structure (i.e. vector space structure over the field $\mathbb K=$ $\mathbb R$ or $\mathbb C$, actually the definition applies also to modules).
Basis in the sense of Hamel.
Given a vector space $V$ over the field $\mathbb K$, a set $B \subset V$ is called algebraic basis or Hamel basis, if its elements are linearly independent and every $v \in V$ can be decomposed as: $$v = \sum_{b \in B} c_b b$$
for a finite set of non-vanishing numbers $c_b$ in $\mathbb K$ depending on $v$.
Completeness of $B$ means here that the set of finite linear combinations of elements in $B$ includes (in fact coincide to) the whole space $V$.
Remarks.
This definition applies to infinite dimensional vector spaces, too. Existence of algebraic bases arises from Zorn's lemma.
It is possible to prove that all algebraic bases have same cardinality.
Decomposition of $v$ over the basis $B$ turns out to be unique.
(2) Banach space structure (i.e. the vector space over $\mathbb K$ admits a norm $||\:\:|| : V \to \mathbb R$ and it is complete with respect to the metric topology induced by that norm).
Basis in the sense of Schauder.
Given an infinite dimensional Banach space $V$ over the field $\mathbb K = \mathbb C$ or $\mathbb R$, a countable ordered set $B := \{b_n\}_{n\in \mathbb N} \subset V$ is called Schauder basis, if every $v \in V$ can be uniquely decomposed as: $$v = \sum_{n \in \mathbb N} c_n b_n\quad (2)$$
for a set, generally infinite, of numbers $c_n \in \mathbb K$ depending on $v$ where the convergence of the sum is referred both to the Banach space topology and to the order used in labelling $B$. Identity (2) means:
$$\lim_{N \to +\infty} \left|\left|v - \sum_{n=1}^N c_{n} b_n\right|\right| =0$$
Completeness of $B$ means here that the set of countably infinite linear combinations of elements in $B$ includes (in fact coincide to) the whole space $V$.
Remarks.
The elements of a Schauder basis are linearly independent (both for finite and infinite linear combinations).
An infinite dimensional Banach space also admits Hamel bases since it is a vector space too. However it is possible to prove that Hamel bases are always uncountable differently form Schauder ones.
Not all infinite dimensional Banach space admit Schauder bases. A necessary, but not sufficient, condition is that the space must be separable (namely it contains a dense countable subset).
(3) Hilbert space structure (i.e. the vector space over $\mathbb K$ admits a scalar product $\langle \:\:| \:\:\rangle : V \to \mathbb K$ and it is complete with respect to the metric topology induced by the norm
$||\:\:||:= \sqrt{\langle \:\:| \:\:\rangle }$).
Basis in the sense of Hilbert (Riesz- von Neumann).
Given an infinite dimensional Hilbert space $V$ over the field $\mathbb K = \mathbb C$ or $\mathbb R$, a set $B \subset V$ is called Hilbert basis, if the following conditions are true:
(1) $\langle z | z \rangle =1$ and $\langle z | z' \rangle =0$
if $z,z' \in B$ and $z\neq z'$, i.e. $B$ is an orthonormal system;
(2) if $\langle x | z \rangle =0$ for all $z\in B$ then $x=0$ (i.e. $B$ is maximal with respect to the orthogonality requirment).
Hilbert bases are also called complete orthonormal systems (of vectors).
The relevant properties of Hilbert bases are fully encompassed within the following pair of propositions.
Proposition. If $H$ is a (complex or real) Hilbert space and $B\subset H$ is an orthonormal system (not necessarily complete) then, for every $x \in H$ the set of non-vanishing elements $\langle x| z \rangle$ with $z\in B$ is at most countable.
Theorem. If $H$ is a (complex or real) Hilbert space and $B\subset H$ is a Hilbert basis, then the following identities hold, where the order employed in computing the infinite sums (in fact countable sums due to the previous proposition) does not matter:
$$||x||^2 = \sum_{z\in B} |\langle x| z\rangle|^2\:, \qquad \forall x \in H\:,\qquad (3)$$
$$\langle x| y \rangle = \sum_{z\in B} \langle x|z \rangle \langle z| y\rangle\:, \qquad \forall x,y \in H\:,\qquad (4)$$
$$\lim_{n \to +\infty} \left|\left| x - \sum_{n=0}^N z_n \langle z_n|x \rangle \right|\right| =0\:, \qquad \forall x \in H \:,\qquad (5)$$
where the $z_n$ are the elements in $B$ with $\langle z|x\rangle \neq 0$.
If an orthonormal system verifies one of the three requirements above then it is a Hibertian basis.
Completeness of $B$ means here that the set of infinite linear combinations of elements in $B$ includes (in fact coincide to) the whole space $H$.
Remarks.
The elements of a Hilbert basis are linearly independent (both for finite and infinite linear combinations).
All Hilbert spaces admit corresponding Hilbert bases. In a fixed Hilbert space all Hilbert bases have the same cardinality.
An infinite dimensional Hilbert space is separable (i.e. it contains a dense countable subset) if and only if it admits a countable Hilbert basis.
An infinite dimensional Hilbert space also admits Hamel bases, since it is a vector space as well.
In a separable infinite dimensional Hilbert space a Hilbert basis is also a Schauder basis (the converse is generally false).
FINAL COMMENTS.
Identities like this:
$$ \sum_n \phi_n(x) \phi_n^*(x') = \frac{1}{w(x)}\delta(x-x') \,\qquad (6)$$
stay for the completeness property of a Hilbert basis in $L^2(X, w(x)dx)$: Identity (6) is nothing but a formal version of equation (4) above.
However such an identity is completely formal and, in general it does not hold if $\{\phi_n\}$ is a Hilbert basis of $L^2(X, w(x)dx)$ (also because the value of $\phi_n$ at $x$ does not make any sense in $L^2$ spaces, as its elements are defined up to zero measure sets and $\{x\}$ has zero measure). That identity sometime holds rigorously if (1) the functions $\phi_n$ are sufficiently regular and (2) the identity is understood in distributional sense, working with suitably smooth test functions like ${\cal S}(\mathbb R)$ in $\mathbb R$.
In $L^2(\mathbb R, d^nx)$ spaces all Hilbert bases are countable. Think of the basis of eigenvectors of the Hamiltonian operator of an Harmonic oscillator in $L^2(\mathbb R)$ (in $\mathbb R^n$ one may use a $n$ dimensional harmonic oscillator). However, essentially for for practical computations it is convenient also speaking of formal eigenvectors of, for example, the position operator: $|x\rangle$. In this case, $x \in \mathbb R$ so it could seem that $L^2(\mathbb R)$ admits also uncountable bases. It is false! $\{|x\rangle\}_{x\in \mathbb R}$ is not an orthonormal basis. It is just a formal object, (very) useful in computations.
If you want to make rigorous these objects, you should picture the space of the states as a direct integral over $\mathbb R$ of finite dimensional spaces $\mathbb C$, or as a rigged Hilbert space. In both cases however $\{|x\rangle\}_{x\in \mathbb R}$ is not an orthonormal Hilbertian basis. And $|x\rangle$ does not belong to $L^2(\mathbb R)$.
Hilbert bases are not enough to state and prove the spectral decomposition theorem for normal operators in a complex Hilbert space. Normal operators $A$ are those verifying $AA^\dagger= A^\dagger A$, unitary and self-adjoint ones are particular cases.
The notion of Hilbert basis is however enough for stating the said theorem for normal compact operators or normal operators whose resolvent is compact. In that case, the spectrum is a pure point spectrum (with only a possible point in the continuous part of the spectrum). It happens, for example, for the Hamiltonian operator of the harmonic oscillator. In general one has to introduce the notion of spectral measure or PVM (projector valued measure) to treat the general case.
This is indeed possible only in some situations, e.g. when the continuous spectrum is absent (it may also consist of a single point, see Valter Moretti's comment below). A sufficient condition for that to be true is that either the Hamiltonian is compact or it has compact resolvent.
Sadly, very few interesting Hamiltonians satisfy that property (an example being the harmonic oscillator). In general, the solution of the Schrödinger equation exists for any initial condition $\psi_0\in\mathscr{H}$ (the Hilbert space), using the unitary one-parameter strongly continuous group $e^{-it H}$ associated to the self-adjoint Hamiltonian $H$ by Stone's theorem. The solution at any time $t\in \mathbb{R}$ is then simply written
$$\psi(t)=e^{-itH}\psi_0\; .$$
Such solution is continuous in time, and with respect to initial data, but it is differentiable in time only if $\psi_0\in D(H)$, where $D(H)$ is the domain of the self-adjoint operator $H$. In the language of analysis of PDEs, that means that the Schrödinger equations, for self-adjoint Hamiltonians, are globally well posed on $\mathscr{H}$.
Best Answer
There are two concepts of duality for vector spaces.
One is the algebraic dual that is the set of all linear maps. Precisely, given a vector space $V$ over a field $\mathbb{K}$, the algebraic dual $V_{alg}^*$ is the set of all linear functions $\phi:V\to \mathbb{K}$. This is a subset of $\mathbb{K}^V$, the set of all functions from $V$ to $\mathbb{K}$. The proof you can see on math overflow uses, roughly speaking, the fact that the cardinality of $\mathbb{K}^V$ is strictly larger than the cardinality of $\mathbb{K}$ if $V$ is infinite dimensional and has at least the same cardinality as $\mathbb{K}$.
The other concept is the topological dual, that can be defined only on topological vector spaces (because a notion of continuity is needed). Given a topological vector space $T$, the topological dual $T_{top}^*$ is the set of all continuous linear functionals (continuous w.r.t. the topology of $T$). It is a proper subset of the algebraic dual, i.e. $T_{top}^*\subset T_{alg}^*$.
The usual example are Hilbert spaces, where the Riesz representation theorem holds (see my comment above): any object of the topological dual $H^*_{top}$ of a Hilbert space $H$ can be identified via isomorphism with an element of $H$. So an Hilbert space and its dual are the "same".
Note however that the topological dual is always thought to be "bigger (or maybe equal)" than the original space. I am very non-precise here, but I think the following example clarifies. Think to the distributions $\mathscr{S}'(\mathbb{R})$. This is the topological dual of the functions of rapid decrease $\mathscr{S}(\mathbb{R})$. Any $f\in \mathscr{S}$ is isomorphic to a distribution in $\mathscr{S}'$, but the converse is obviously not true: there are distributions that are not functions (the Dirac's delta), and in general any $L^p$-space is thought as a subset of $\mathscr{S}'$ (so $\mathscr{S}'$ is quite "big").