Tom, I agree with everything you wrote except your suggestion that keys should be stable:
redo the model so that every relation has a stable natural key
Stability is usually a desirable property for a key and is certainly an important consideration but it isn't an absolute requirement. Sometimes it may be quite reasonable to implement keys that are unstable by design. One example is a login name attribute. The user may be allowed to change his login name at any time. The login name must remain unique though, so it's perfectly sensible to make it a key in the database.