Is it safe to use "real" keys in NSLocalizedString()? Is there a guaranteed fallback language?

To answer your question: Yes, I have experienced the issue you are worrying about, i.e. the key names showed up even though a localizable.strings file was present and included entries for those key names. This happens when you have more than one localizable.strings files in your project. Which can easily happen if you drop a set of files from an Open Source project that has their own localizable.strings (such as ShareKit) into your project.

Here is a related question that discusses this issue.

But at least if you use ID-style key names, you would notice such a problem when you test your app in any language. If you used the English (or base language) string as the keys, then you wouldn't see this insidious problem until you test the localized versions and it could slip by unnoticed more easily.

So on top of your point on having to remember to update the keys (in all languages) when rewording text, there is the issue of potentially hiding bugs when using the English text as key (English would look OK, but localized versions wouldn't). Therefore it seems to me that using "real" key names rather than actual text is more practical. If you are still worried that for some reason the key names might show up, pick a key that is at least descriptive enough to be understandable.