What is "the exception that proves the rule"?

I've heard the phrase, "the exception that proves the rule," but it's not clear to me what it means. It sounds self contradictory. What is a good example of "an exception that proves the rule?" Can this phrase be used effectively in formal dialog, or is it only colloquial?

The least stupid usage I have encountered for this phrase -- no real idea whether it's actually to do with its origins -- is when a rule expresses a tendency or preference rather than a hard-and-fast delineation, and the difficulty encountered in going against that tendency demonstrates the force of the rule.

A random example might be a rule that "bears do not dance". The amazing Dr. Florenheimer trains a bear to dance in his traveling circus. This forms an exception to the rule, but the years that it took Dr. Florenheimer to train the bear, along with the expense and injuries to staff, make it an exception that "proves" the rule, in some sense -- at the least, proving that it may not be violated lightly.

The phrase has its origin in the law. It means that a law written in broad terms, but provided with an exception for some special case, is properly understood broadly; because the authors of the law saw fit to make a special exception for special cases.

So

Driving is not allowed in the park.

is a very broad rule that make no allowance for special cases, and one might see fit to interpret it with some leniency, perhaps allowing ambulances, police cars and early morning deliveries to venues in the park.

On the other hand

Driving is not allowed in the park except for emergency vehicles.

shows that the author has explicitly considered what special cases might merit an exception. So the rule should be interpreted broadly, and delivery vehicles excluded.

The existence of the exception proves that the author meant what he or she said and that the rule applies to cases not excepted.