Relay errors with exist key id

@jauer, @untitaker - thoughts?