Feedback Letter
Before the 19th century, scientists and mathematicians were caught up in the Enlightenment fever of figuring out nature's "laws" as Newton did in Principia and since much of what high school education teaches in science class was discovered in this time, students grow up with the idea that there are inviolable "laws" in science.
What happened in the 19thC was the discovery of several paradoxes in mathematics which made mathematicians realize that their "theorems" (which is basically what "laws" are called in mathematics) must be rigorously proved. Before this, many discoveries in mathematics were done in the same way as science, i.e, by observation. As any decently educated math major can tell you now, no matter how many billions of cases in which an idea may hold, that does not prove it. To prove a theorem requires a rigorous proof which eliminates the possibility of that theorem being wrong.
This is why that although Newton and Leibniz are credited with discovering Calculus, the calculus that is taught today is the work of Riemann et. al. during the 19th C who rigorously proved the relationship between derivatives and integration (a modernday educated mathematician reading Principia would find Newton's work to be nonsense, as one of my professors told me).
This brings us back to science: science is done through observation, and scientists (physicists in particular) will formulate some equation that explains observed phenomena (think Newton's laws). As time progresses, scientists will collect thousands and millions of observations that may or may not support this equation. If in some scenario, a billion observations support this equation, that does not by any means rule out the possiblity that this equation might be shown to be wrong by some observation in the future. Therefore, this equation or idea or principle can never be proven.
As scientists and rational people, we can approach very high degrees of certainty but can never have absolute certainty as we do in mathematics. That is why science deals with theory and mathematics deals in theorems. ( I like to use the analogy of the asymptote, the "law" is the asymptotic limit, while every observation brings us closer and closer to the asymptotic limit but only at infinity is that limit reached).
I strongly suspect had the idea of rigorous proofs emerged before the discoveries of the 16th and 17th centuries, we would today have "Newton's Theory of Motion" and "Newton's Theory of Gravity". We have "Einstein's Theory of Relativity" despite relativity's ability to describe the movement of celestial bodies to a much much MUCH MUCH higher degree than Newton's "laws". Likewise, had the idea of rigorous proofs emerged after Darwin formulated evolution in "Species" we would today call it "the law of evolution" rather than the "theory of evolution".
In short, what scientists call a "theory" is identical to what scientists called a "law" before the 19th C, i.e. a set of explanations based on observation that explains nature. The difference is that in the 19th century, we attained a deeper understanding of logic and what it takes to "prove" an idea.
Taking the creationists' argument that evolution is just a theory and clearly we should teach "alternatives" to its logical end, this would mean teaching aristotle's idea of motion and "impetus" because Newton's "laws" of motion is simply a "theory" (and a theory that has been shown to be wrong in extreme cases mind you).
I find it tragic that those who would disparage evolution do not understand this, but not surprising. Those who dismiss evolution as "theory" probably never had an education in science and a basic understanding of how science works, or more importantly LOGIC, and therefore subscribe to the idea of "laws". Well....except for Michael Behe whom I suspect has just lost his mind and/or is out to make a buck because he has no fear of losing his job due to tenure.
Response
In the philosophy of science there is a long tradition of discussing what laws and theories are. Most people seem to think that theories include models (mathematical models) that can be axiomatised - that is, reduced to a logicomathematical form with certain fixed assumptions, but not everyone does.
A law is traditionally a general statement without exception - as you note, many of Newton's "laws" and several others (such as the Ideal Gas Law) have been shown not to be exceptionless. Physicists have no trouble adopting those laws as working generalisations. Only philosophers appear to have trouble with it.
So there is a close relationship between "theory" in science and "law", in that, the "law" is the core mathematical component of the theoretical explanation. That said, many theories do not start life as mathematical - often they are verbal and metaphorical, and are formalised later - such is what happened to the theory of natural selection, and more recently, to speciation.
I very much like your notion of rigorous proof being the reason why "law" dropped out of sight in science. I suspect, though, that this is not uniform across all sciences.