This quest is very challenging, but fun and replayable due to the random nature of the bosses and locations. With these two decks, we beat it about 90% of the time, only losing when we got a ridiculous run of bad locations in a row. Location lock and/or threating out is the most likely way to lose this.
These decks have been good in that even with bad draws, you can still find ways to win with the cards that you do draw.
First player should mulligan for Unexpected Courage. It's one of the most important cards. The first UE should 100% go on Beregond, the second UE usually on Beregond again, and the third on Legolas. It's usually a waste to put it on Elrond, as Player 2 should be doing almost all the sentinel defending with Beregond. If Elrond gets Light of Valinor, then you can quest him, and after that, you rarely use him in a round, so you if you have Vilya, you can usually use that later in the round.
Other important cards for Player 1 are Light of Valinor, Warden of Healing, Test of Will, Galadhrim's Greeting, Arwen Undomiel, Northern Tracker, Dwarven Tomb, Master of the Forge.
Ideally, Beregond becomes an unkillable tank who can sentinel defend 2/3 times a round, Legolas becomes a ranged killing machine, and Player 1 foils bad Treacheries with either Eleanor or Test of Will. Player 1 also needs to do 90% of the questing, lower the threat of both players, and often needs to get a healer into play to remove light damage from heroes.