Chemistry - Semi-Infinite Potential Square Well: Negative Potential
Answering your quantum mechanics question seems to become a hobby of mine :). First let me say that there is nothing wrong with shifting the potential up so that $V_{0} = 0$. This choice would indeed simplify the problem as it gets rid of negative energy values and thus avoids the following point of confusion: when $E < 0$ the wave function of a particle in region $\text{II}$ is not a plane wave $\mathrm{e}^{\mathrm{i} k x}$ ($k \in \mathbb{R}$) like that of a free particle moving in vacuum but a decaying exponential $\mathrm{e}^{-\kappa x}$ (with $\kappa \in \mathbb{R}$). So, the choice $V_{0} = 0$ is advisable. Shifting the potential back later is always possible and might be easier.
Nevertheless, of course the problem is solvable irrespective of the choice of $V_{0}$. I think your problem in this case is that you enforced an incorrect boundary condition. To avoid confusion I will start from the beginning:
I will only consider the case $E < 0$ in the following, so $E$ is always a negative number between $-V_{0}$ and $0$. For region $\text{II}$ you have to solve the Schroedinger Equation:
\begin{align} - \frac{\hbar^{2}}{2m} \frac{\mathrm{d}^{2} \psi_{\text{II}}(x)}{\mathrm{d} x^{2}} &= E \psi_{\text{II}}(x) \\ \frac{\mathrm{d}^{2} \psi_{\text{II}}(x)}{\mathrm{d} x^{2}} &= - \frac{2mE}{\hbar^{2}} \psi_{\text{II}}(x) \ . \end{align}
Ok, here comes the first "problem" with the choice of $V_{0}$: In your solution you chose $\frac{2mE}{\hbar^{2}} = k^{2}$ as you would naturally do for a free particle. But since $E$ is negative $k$ will be a complex number (and not a real number as it would be for a free particle) and so this differential equation does not have an oscillatory solution $\psi_{\text{II}}(x) = A \sin(kx) + B \cos(kx)$ with $k \in \mathbb{R}$. Rather you get a decaying exponential function by doing the following: $- \frac{2mE}{\hbar^{2}}$ will be a positive number so you simply set $- \frac{2mE}{\hbar^{2}} = \kappa^{2}$ to get
\begin{align} \frac{\mathrm{d}^{2} \psi_{\text{II}}(x)}{\mathrm{d} x^{2}} &= \kappa^{2} \psi_{\text{II}}(x) \qquad \quad \text{with} \qquad \kappa \in \mathbb{R} \ . \end{align}
Now, this differential equation has a solution of the form
\begin{align} \psi_{\text{II}}(x) = A_{\text{II}} \mathrm{e}^{\kappa x} + B_{\text{II}} \mathrm{e}^{-\kappa x} \qquad \quad \text{with} \qquad \kappa \in \mathbb{R} \ . \end{align}
At this point you can enforce the boundary condition that the wavefunction $\psi_{\text{II}}$ must be square integrable over the whole interval $a < x < \infty$ (Note that you don't have to consider the interval $-\infty < x < \infty$ but only the interval on which $\psi_{\text{II}}$ is defined). Since $\lim_{x \to \infty} \mathrm{e}^{\kappa x} = \infty$ this mean that the prefactor $A_{\text{II}}$ must be equal to zero, so
\begin{align} \psi_{\text{II}}(x) = B_{\text{II}} \mathrm{e}^{-\kappa x} \qquad \quad \text{with} \qquad \kappa \in \mathbb{R} \ . \end{align}
So much for region $\text{II}$. Let's move on to region $\text{I}$: Here you have to solve the Schroedinger Equation:
\begin{align} - \frac{\hbar^{2}}{2m} \frac{\mathrm{d}^{2} \psi_{\text{I}}(x)}{\mathrm{d} x^{2}} - V_{0} \psi_{\text{I}}(x) &= E \psi_{\text{I}}(x) \\ \frac{\mathrm{d}^{2} \psi_{\text{I}}(x)}{\mathrm{d} x^{2}} &= - \frac{2m(E + V_{0})}{\hbar^{2}} \psi_{\text{I}}(x) \ . \end{align}
Again, care must be taken: Since $-V_{0} < E < 0$ the term $(E + V_{0})$ is positive and so $- \frac{2m(E + V_{0})}{\hbar^{2}}$ is a negative number and you can set $- \frac{2m(E + V_{0})}{\hbar^{2}} = -k^{2}$ which leads to
\begin{align} \frac{\mathrm{d}^{2} \psi_{\text{I}}(x)}{\mathrm{d} x^{2}} &= - k^{2} \psi_{\text{I}}(x) \qquad \quad \text{with} \qquad k \in \mathbb{R} \ . \end{align}
This differential equation has a solution of the form:
\begin{align} \psi_{\text{I}}(x) = A_{\text{I}} \mathrm{e}^{\mathrm{i} k x} + B_{\text{I}} \mathrm{e}^{-\mathrm{i} k x} \qquad \quad \text{with} \qquad k \in \mathbb{R} \ . \end{align}
(You could also formulate an equivalent solution in terms of $\sin$ and $\cos$ functions using Euler's formula if that is more to your liking. But I prefer plane waves ;)) This is the point where you made your main mistake: You discarded one of the terms in your $\psi_{\text{I}}$ wavefunction because it blew up for $x \to \infty$. But $\psi_{\text{I}}(x)$ is only defined on the interval $0 \leq x \leq a$ and within this interval both exponential terms are perfectly square-integrable and you can't discard any of them.
Finally, you just have to remember that $\psi_{\text{III}}(x) = 0 \ \forall \ x$ and enforce the boundary conditions given by the system:
\begin{align} \psi_{\text{I}}(0) &= \psi_{\text{III}}(0) \quad &&\Rightarrow \quad A_{\text{I}} \mathrm{e}^{0} + B_{\text{I}} \mathrm{e}^{0} = 0 \quad &&\Rightarrow \quad B_{\text{I}} = -A_{\text{I}} \\ \psi_{\text{I}}(a) &= \psi_{\text{II}}(a) \quad &&\Rightarrow \quad A_{\text{I}} \mathrm{e}^{\mathrm{i} k a} - A_{\text{I}} \mathrm{e}^{-\mathrm{i} k a} = B_{\text{II}} \mathrm{e}^{-\kappa a} && \\ & &&\hphantom{\Rightarrow} \ \quad A_{\text{I}} \underbrace{\bigl(\mathrm{e}^{\mathrm{i} k a} - \mathrm{e}^{-\mathrm{i} k a} \bigr)}_{= \, 2 \mathrm{i} \sin(k a)} = B_{\text{II}} \mathrm{e}^{-\kappa a} \quad &&\Rightarrow \quad B_{\text{II}} = 2 \mathrm{i} \sin(k a) \mathrm{e}^{\kappa a} A_{\text{I}} \end{align}
Edit:
Concerning your comment: You can indeed enforce another boundary condition. The probability flux is required to be continuous across any surface, since otherwise the surface would contain sources or sinks. This entails the requirement that both $\psi$ and $\nabla \psi$ must be continuous. The continuity condition $\psi_{\text{I}}(a) = \psi_{\text{II}}(a)$ has already been enforced but the one for the gradient is still left:
\begin{align} \frac{\mathrm{d} \psi_{\text{I}}(x)}{\mathrm{d} x} \bigg|_{x = a} &= \frac{\mathrm{d} \psi_{\text{II}}(x)}{\mathrm{d} x} \bigg|_{x = a} \ . \end{align}
From the above discussion we know that:
\begin{align} \psi_{\text{I}}(x) &= A_{\text{I}} \underbrace{\left(\mathrm{e}^{\mathrm{i} k x} - \mathrm{e}^{-\mathrm{i} k x} \right)}_{= \, 2 \mathrm{i} \sin(k x)} = 2 \mathrm{i} A_\text{I} \sin (kx) = C_\text{I} \sin(kx) \end{align}
and
\begin{align} \psi_{\text{II}}(x) &= \underbrace{2 \mathrm{i} A_{\text{I}} \sin(k a)}_{= \, \psi_{\text{I}}(x=a)} \, \mathrm{e}^{\kappa a} \mathrm{e}^{- \kappa x} = \psi_{\text{I}}(x \! = \! a) \, \mathrm{e}^{- \kappa (x - a)} \end{align}
with $C_\text{I} = 2 \mathrm{i} A_{\text{I}}$, so
\begin{align} \frac{\mathrm{d} \psi_{\text{I}}(x)}{\mathrm{d} x} \bigg|_{x = a} &= \frac{\mathrm{d} \psi_{\text{II}}(x)}{\mathrm{d} x} \bigg|_{x = a} \\ k C_\text{I} \cos(ka) &= - \kappa C_\text{I} \sin(ka) \\ \kappa &= - \frac{k}{\tan(k a)} \ . \end{align}
While this equation looks innocent enough it is not easily solved for $E$ and you will need the assistance of something like Mathematica for that.