You need proof he lost the key, in other Words you need the key, to show her. However I found it more rewarding giving the key to the orc who lost it, and then being able to kill him later for more reward (including key)