Your "imaginary eigenvalues" don't work, because the eigenfunctions are no eigenfunctions. They do not lie in $L^2$, as you seem to be aware of.
So, let's deal with the Laplacian itself: $-\Delta=-\frac{d^2}{dx^2}$.
What I want to do is, I want to calculate the Fourier transform of this operator, because the Fourier transform diagonalizes $-\Delta$, as we will see. From the diagonal form, we can read off the spectrum and thus conclude that the spectrum consists of $\mathbb{R}^+$. Of course, I don't answer the question "why $e^{ikx}$ are enough for real $k$", simply because it's a meaningless question in the Hilbert space setting.
So, let's do it. Take a function $\psi\in L^2(\mathbb{R})$ and calculate:
$$ \mathcal{F}(-\Delta \psi)(k)=\int e^{ikx}\left(-\frac{d^2}{dx^2}\right)\psi(x)\,dx = \int k^2e^{ikx}\psi(x)\,dx = k^2 \mathcal{F}(\psi)(k) $$
where we integrated by parts two times (using that $\psi$ necessarily vanishes at infinity) and then differentiated $e^{ikx}$. This formula means that $\mathcal{F}$ diagonalizes the Laplacian, because we have just seen that the Fourier transform of the Laplacian $\mathcal{F}(-\Delta)\mathcal{F}^*$ is a multiplication operator. The idea is now that from a multiplication operator, we can read off the spectrum: It's the essential range of the multiplication operator. Just from the definition, we can see that this will be $[0,\infty)$ in our case, hence $\sigma(-\Delta)=[0,\infty)$.
At no point did we even talk about $e^{ikx}$, so how to solve the $e^{ikx}$ with imaginary $k$ business? You don't have to - none of these functions is in $L^2$, but: if you now put in $\psi(x)=e^{ikx}$ with real $k$ (because $k$ is real in the Fourier transform!), then it looks like it is an eigenfunction of $-\Delta$. In other words: If you imagine a space with your basis being the functions $e^{ikx}$, then the Fourier transform of the Laplacian is just the infinite matrix with eigenvalues $k^2$ on the diagonal. However, this is not the rigorous picture!
Edit: A very good explanation with more maths can be found here: https://math.stackexchange.com/questions/766479/what-is-spectrum-for-laplacian-in-mathbbrn
Note that this is not easy maths, but in order to understand the finer points of this business, you can't avoid it.