Here is another form of the same inconsistency:

>>> [].pop(0)
IndexError: pop from empty list
>>> {}.pop(0)
KeyError: 'pop(): dictionary is empty'

And my preferred one:
>>> unicodedata.lookup('"')
KeyError: 'undefined character name \'"\''

KeyError is special in that dict lookup raises the equivalent of
KeyError(key). Since the key may be any kind of (hashable) object, it's
preferable to repr() it.

I can see 3 solutions to the problem:

1- imitate IndexError for lists: the exception do not contain the key.

2- dict lookup builds the complete string message, and raise it
   raise KeyError("key not found: %r" % key)
then KeyError.__str__ can be removed.

3- like IOError, KeyError has "msg" and "key" attributes. then dict
lookup raises
   raise KeyError("key not found", key)
and KeyError.__str__ is something like:
   if self.key is not None:
       return "%s: %r" % (self.msg, self.key)
   else
       return str(self.msg)

Choice 1 is not an improvement.
Choice 2 has the correct behavior but leads to performance problems;
KeyErrors are very very common in the interpreter (namespace lookups...)
and formatting the message is costly.
Choice 3 may cause regression for code that use exception.args[0], but
otherwise seems the best to me. I'll try to come with a patch.