Thanks to Ivan for pointing out these two papers to me. One is a short paper titled "Guns and Butter: Towards formal axioms of input validation" by Robert J Hansen and Meredith L Patterson. The second is a presentation called "Stopping injection attacks with computational theory" again by the same two guys. As the URL's give away these are papers from the recent Black Hat briefings in Las Vegas. Both papers present new theories on input validation that promise convenience and security and they talk about the problem of false negatives and false positives and why regular expressions are not the answer, Finite State Automata, and computational theory are.
These are great papers and are worth reading.