Have Fun Storming the Castle!
"Have fun storming the castle!" -- Miracle Max, the Princess Bride
My two-handed fellowship that defeated Fortress of Nurn. Spoilers for that scenario will be in this description. After constructing decks with this hero lineup, it took 6 tries for a win, with a few little changes to the decks after each loss. The decks perform very consistently well and get far versus this scenario every time I play, so while I can't guarantee a "one and done" win with this scenario, I can say you'll be able to hold your own and get far on almost every attempt (I did have one and only one turn-two scoop because Beregond died).
There were a couple of basic things I wanted to accomplish in order to counter this scenario, aside from standard game mechanics like "manage threat":
1-Bring healing on turn 1. Hence Glorfindel, and Elrond to make his ability more powerful. The scenario can steal away all of your healing cards, but healing is important in this scenario.
2-Counter direct damage effects: no 1-hit point allies allowed.
3-Be able to strike for 13 at once to counter Khamul, and 12 on turn 1 in case a troll is revealed early on. That can be accomplished with a turn-1 undefended attack on Gimli, bringing him to 6 attack strength, 11 with Beorn, and 1 from Balin if you hold him back from the quest (your attacking allies are too expensive to play on turn 1, so you have to rely on heroes at first). I usually quested with Balin anyway.
4-Allow Gimli to survive that turn-1 undefended attack consistently. Balin can replace the shadow effect, making this a lot more likely. After that, his ability is just very useful, and he provides willpower.
5-Turtle on stage 1 of the quest and avoid Power of Mordor cards. Therefore, player side quests. Double Back is the most important of the whole lot, but Keeping Count is also very nice too. The rest are just OK. In my winning game I actually cleared The Storm Comes twice (second one just goes to your discard pile), just to stall for time.
I'll leave the rest of the strategy to the individual deck descriptions. Thanks for reading!