If the only way that client code can call with invalid keys, sanitize that input in a central place before passing it on to the rest of the program. Sounds like after that input has been checked, it would be a program fault if an invalid key was supplied, so then you can handle that with exceptions and return references to your data.
Sticking to pointers and checking null everywhere because there may have been an invalid key supplied at the command line seems wrong to me.
So while you'll probably still need some way of checking that the colleciton contains the key->value mapping, you only need to do it once when the key is received from the user.
Speaking in terms of a generic collection object, a return value of NULL from your function value* getThing(const key&); ) could mean that the key is mapped onto NULL or that the key is not in the map. You've already mentioned that keys will not be mapped onto null values, so in this instance a return value of NULL can only mean that the key is not in the collection. However will that always be the case? Are you intending to re-use the collection? Also someone updating the code in the future may not immediatly appreciate that a return value of NULL can only be generated when the key isn't mapped. Therefore, while NULL checks would work, I think adding explicit 'exists' checks could make your code easier to read and make the collection class more re-usable.
Both of your suggestions look like fine choices.
Another option you might want to consider, (although I'd still go with the 'bool exists(const key&)' suggestion) is to have your collection return a default object when the key isn't stored. The object would be an instance of a default class, extending the class of the values stored in the collection, but stubbing out all procedures so that they do nothing and all functions so that they return neutral values. Then the rest of your code can process the default object as if a key-value map was found, removing the need for any 'exists' or 'is NULL' checks. (The NULL Object pattern, from Robert Martin's book 'Agile Softwaree Development: Principles, Patterns and Practices')