I have been getting better results using a low level hero (7) prior to this I had over 300 battles with only minor success, using lv45+ hero.
Think about the mechanics of the Quests, you would only have a low lv hero when you start to conquer valleys