The current behavior seems to be a recurring source of confusion and bugs, so something needs to change.  I'm thinking that the least egregious thing to do is to remove (in 3.6) the special case code for KeyError.  The small downside is that KeyError('')  wouldn't look as good.  The benefit is that we eliminate an unexpected special case and make KeyErrors behave like all the other exceptions including LookupError. 

I'm against the two-args solution as being too disruptive.  Since args[0] is currently the only reliable way of extracting the key, prepending a message field will likely break much existing code that really wants to access the key.