Why isn't the wave equation $\nabla^2 \psi - 1/c^2 \partial_{tt} \psi = (\frac{mc}{\hbar})^2\psi$ Special relativity was well established by the time the schrodinger equation came out. Using the correspondence of classical energy with frequency and momentum with wave number, this is the equation that comes out, and looks sensible because this is of the form of a wave equation, like the one for sound etc, except with an inhomogeneous term
$$\nabla^2 \psi - 1/c^2 \partial_{tt} \psi = (\frac{mc}{\hbar})^2\psi$$
Instead, we have schrodinger's equation which reminds of the heat equation as it is first order in time. 
EDIT Some thoughts after seeing the first posted answer
What is wrong with negative energy solutions? When we do freshman physics and solve some equation quadratic in, say, time... we reject the negative time solution as unphysical for our case. We do have a reason why we get them, like, for the same initial conditions and acceleration, this equation tells usthat given these iniial velocity and acceleration, the particle would have been at the place before we started our clock, since we're interested only in what happens after the negative times don't concern us.  Another example is if we have areflected wave on a rope, we get these solutions of plane progressive waves travelling at opposite velocities unbounded by our wall and rope extent. We say there is a wall, an infinite energy barrier and whatever progressive wave is travelling beyond that is unphysical, not to be considered, etc.
Now the same thing could be said about $E=\pm\sqrt{p^2c^2+(mc^2)^2}$ that negative solution can't be true because a particle can't have an energy lower than its rest mass energy $(mc^2)$ and reject that. 
If we have a divergent series, and because answers must be finite, we say.. ahh! These are not real numbers in the ordinary sense, they are p-adics! And in this interpretation we get rid of divergence. IIRC Casimirt effect was the relevant phenomenon here.
My question boils down to this. I guess the general perception is that mathematics is only as convenient as long as it gives us the answers for physical phenomenon. I feel this is sensible because nature can possibly be more absolute than any formal framework we can  construct to analyze it. How and when is it OK to sidestep maths and not miss out a crucial mystery in physics. 
 A: That's the Klein-Gordon equation, which applies to scalar fields. For fermionic fields, the appropriate relativistic equation is the Dirac equation, but that was only discovered by Dirac years after Schrödinger discovered his nonrelativistic equation. The nonrelativistic Schrödinger equation is a lot easier to solve too.
The relativistic equations admit negative energy solutions. For fermions, that was only resolved by Dirac much later with his theory of the Dirac sea. For bosons, the issue was resolved by "second quantization".
The problem with negative energy solutions is the lack of stability. A positive energy electron can radiate photons, and decay into a negative energy state, if negative energy states do exist.
A: 
"My question boils down to this. I
  guess the general perception is that
  mathematics is only as convenient as
  long as it gives us the answers for
  physical phenomenon. I feel this is
  sensible because nature can possibly
  be more absolute than any formal
  framework we can construct to analyze
  it. How and when is it OK to sidestep
  maths and not miss out a crucial
  mystery in physics."

Your question just took a huge leap sideways. Probably into Soft-question. You don't "sidestep maths" in Physics. You introduce "different math" and look carefully to see whether it fits the experimental data better. People generally pick a particular mathematical structure and try to characterize its differences from the existing best theories, which for the best alternatives takes people decades. There are other issues, such as whether your different maths is more tractable, whether people think it's beautiful, whether it gives a better explanation, whether it suggests other interesting maths, whether it suggests interesting engineering, whether it's simple enough for it to be used for engineering. The wish-list for a successful theory in Physics is quite long and not very articulated. Philosophy of Physics tries to say something about the process and the requirements for theory acceptance, which I've found it helpful to read but ultimately rather unsatisfying. "miss[ing] out a crucial mystery in physics" would be bad, but it's arguably the case that if it's not Mathematics it's not Physics, which in the end of hard practical use will be because if it's not mathematics you'll be hard pressed to do serious quantitative engineering.
For your original question, I've been pursuing why negative frequency components are so bad for about 5 years. If you feel like wasting your time, by all means look at my published papers (you can find them through my SE links) and at my Questions on SE, all of which revolve around negative frequency components (although I think you won't see very clearly why they do in many cases, even if you know more about QFT than your Question reveals). I don't recommend it. I can't at this stage of my research give you a concise Answer to your original Question.
A: It seems to me that the questioner is asking about Quantum Mechanics, not Quantum Field Theory.  So what one can or cannot do in QFT is evading the question.  
The short answer to the question as posed is « Yes, it is the wave equation.»
As prof. Motl pointed out, it was discovered by Schroedinger first, following exactly the reasoning the OP presents.  It does not describe the electron, but it does describe one kind of meson, and so it has to be said that it agrees with experiment.  I emphasise that this is qua relativistic one-particle QM equation, not second-quantised. Both Pauli's lectures in wave mechanics and Greiner's Relativistic Quantum Mechanics treat the K.-G. equation at length as a one-particle relativistic wave equation. Furthermore, the negative energy states can be eliminated by taking the positive square root: 
$$\sqrt{-\nabla ^2 + m^2} \psi = i{\partial \over\partial t}\psi.$$
Every solution of this equation is a solution of the original K.-G. equation, so if the latter is physical, so is this one.  
Now we have an equation that agrees with experiment, does not need any fiddling with the maths, but does not allow the Born-rule probability interpretation of the non-relativistic Schroedinger equation.  What one says about this depends on whether one thinks philosophy, the Born interpretation, should trump experimental data, namely the « mesonic hydrogen » energy levels, or the other way round....
A: You can throw away the negative energy solution if you're just doing relativity and not QM, just like in the examples you mentioned. But if you add QM you can no longer do that: remember the energy spectrum are the eigenvalues of the Hamiltonian (operator), so you just can't throw away some eigenvalues without also throwing away the linear algebra the theory is based upon. 
So no, it is never ok to sidestep math. When you eliminate negative roots of cuadratic equations in classical physics you're not sidestepping math, after all you need to apply the rules of algebra to get the solutions, you're just applying physical considerations to the solutions to get rid of (physiccally) spurious ones that can be ignored without altering the mathematical structure of the theory. In the RQM case the negative energy solutions are unphysical but you can't just ignore them, you have to deal with them.
A: If I'm not mistaken, people have shown that in a scattering problem, even if we start with a wave purely made of positive energies, after the scattering there will be negative components popping up, so it does not make sense to simply throw away the negative energy states. But I can't find the reference now.
