I don't know, "the exception that proves the rule" always made sense to me, even with the current definition of "proves". I've always thought of it as pointing out that if an exception is rare enough to stand out, it demonstrates that the rule is valid, even if not 100% true all the time. If the exception were common enough to not stand out, the rule wouldn't be valid often enough to be stand as a rule.
If that makes any sense ;-). OTOH, that's what's so elegant about that phrase, it expresses a complex hard to describe idea, succinctly and clearly. Which, as another person has already stated, is one factor that makes a good catchphrase valuable.