I got this wrong several times (of course) when I did my first few i10n projects. First time I used the strings as keys and ran into the problem described above. Time after that, I went the 'pure' way and used GUID's as a key which was a pain in the ass to used and caused the wrong messages to show up in some places a few times. It also made the translators hate me a lot. After that I went what I'd describe the 'pragmatic' way. Every time you encounter a string message, you make up a string identifier that sort of describes the message. So 'High importance!' would be e.g. HIGH_IMPORTANCE. But a multi-sentence message might be 'INTRODUCTION_PARA'. If the id already exists, and there is no obvious alternative, you just call it HIGH_IMPORTANCE_2 - in other words, you don't think about the key too much, you just use quick and dirty keys, you don't change them EVER, and you make sure you have good tools to prevent clashes, even across 'module' boundaries (where 'module' can be 'source files', 'shared libraries' or 'projects that use the same string resources').
You also put formatting strings in the messages, and in a way that makes the order configurable by the translator (e.g. using boost::format and not sprintf). You also provide the translator with a UI that shows them the message key, the 'original' message and the translation in various languages that already exists. And you provide a way for the developer/designer to attach notes to each message, where necessary.
Finally you adapt your messages to be as 'neutral' or easy to translate as possible; how to do this is something you learn with experience. And have to test test test and write special cases where necessary, like where you absolutely need things like 'first' or things where you have weird capitalization rules and stuff like that.
I never liked gettext. First, the is the licence, which rules it out for many projects. Secondly many of the functionalities are overkill, and (while 'pure' from an engineering pov) cause more work than they save (the cases I described above as 'just implement something custom in code'). Third, the tools suck. None of the editors I ever tried were really comfortable to use. They must have gotten the last 10 years or so, which was the last time I looked, but usually they're 'open source user experience' quality' - which is fine for developer tools, but not to be used by non-tech users (which most people who end up doing the translations are, because let's face it, translation is usually an afterthought and a low-respect task).