How do we know that PDE solutions obtained via separation of variables are the only ones? You can find solutions to, for example, the 1D Schrödinger equation $-\frac{\hbar^2}{2m}\Psi_{xx}(x,t) + V(x, t)\Psi(x, t) = i\hbar\Psi_{t}(x,t)$ by assuming solutions of the form $\Psi(x,t) = X(x)T(t)$. How do we know that there aren't other (potentially unphysical, but still mathematically valid) solutions where $x$ and $t$ aren't separate? Does the fact that you can arbitrary linear combinations of the separable solutions to construct a new solution "make up" for the fact that we didn't go looking for the non-separable ones?   

We are indeed using separable solutions to build non-separable ones.
Suppose $\psi_1 = e^{-\frac{i}{\hbar}E_1t}\phi_1(x)$ and  $\psi_2 = e^{-\frac{i}{\hbar}E_2 t}\phi_2(x)$ are two solution for the Schrödinger equation, where $\phi_i$'s are the eigenvector of eigenvalue $E_i$ for the operator $H = -\frac{\hbar}{2m}\Delta + V$, then the superposition
$$\psi_{12} = \alpha_1 \psi_1 + \alpha_2 \psi_2$$
is non-separable.
The separability comes from the heuristic that for a state $\psi(x,0)$ "evolves" with time, and using the evolution operator we can get the solution at time $t$:
$$
\psi(x,t) = e^{-\frac{i}{\hbar}H t}\psi(x,0),
$$
which is intrinsically separable for each term in the expansion in the eigenvalues of $H$:
$$
e^{-\frac{i}{\hbar}H t} = \sum_{n} |{\phi_n}\rangle e^{-\frac{i}{\hbar}E_n t}\langle{\phi_n}|,
$$
translated into mathematics notations:
$$
\psi(x,t) = e^{-\frac{i}{\hbar}H t} |\psi_{t=0}\rangle = \sum_{n} |{\phi_n}\rangle e^{-\frac{i}{\hbar}E_n t}\langle{\phi_n}|\psi_{t=0}\rangle = \sum_{n} \alpha_n e^{-\frac{i}{\hbar}E_n t}\phi_n(x),
$$
where $\alpha_n$ is the inner product $\langle{\phi_n}|\psi_{t=0}\rangle$. Each one term is separable, but not $\psi(x,t)$. 
In general, we can get non-separable solution from the evolution of the separable eigen-solution in different energy level.
Aside from Christopher A. Wong said about existence and uniqueness, another reason why we are more interested in the separable solution is because of its physical meaning, for example time harmonic wave $\psi(x,t) = e^{-i\omega t} \phi(x)$.
