“You can trust us to stick with you through thick and thin — to the bitter end. And you can trust us to keep any secret of yours — closer than you keep it yourself. But you cannot trust us to let you face trouble alone, and go off without a word. We are your friends, Frodo.” — Merry, The Fellowship of the Ring
This is the deck I used to beat the Fortress of Nurn. It is a variation of the classical Vilya deck that uses the synergy between Elrond, Vilya and Gandalf to play high-cost allies. The deck includes a lot of singleton uniques to ensure that you only rarely will have something on top of your deck that you already have in play. Ideally you should get Light of Valinor (or Unexpected Courage if necessary) on Elrond so he can pump out allies or attachments every turn. At some point you also want to put either Shadowfax or UE on Gandald In a pinch, use Wizard's pipe to swap out the top card. Once you have six allies in play, the contract will fire, making your band of heroes truly formidable. A few allies are more important for success, and I have therefore included two copies. This includes Firyal (to control the encounter deck), Glorfindel (because you can ready him with spare copies of uniques and he is a fantastic ally) and Jubayr (because his shadow card control means that you can avoid nasty surprises, and because you can ready him after you declare him as a defender with Narya, ensuring that he can block twice). Steward of Gondor should go on Elrond, because he can pay for allies of all spheres. In hindsight, the deck doesn't really need a very good tale, and I would probably swap it for more readying or an additional test of will. In your opening hand you want Vilya, potentially a wizard's pipe and Light of Valinor /UE. If you have Vilya, don't mulligan.
Some pointers about Fortress of Nurn specifically: In the first stage, keep on the pressure. It is easy to get stuck turtling, allowing your deck to run out of cards. This blocks your tempo, and you should therefore prioritize to blast through the first stage if you can. This will probably lead to some resets, but I found it necessary for success. Think carefully about your board stage before you decide what Power of Mordor card you decide to pick. Usually, the one the Armies of Mordor card is not so bad, especially if you get Jubayr in play. I also picked the Nazgul enemy, because Eowyn can deal with him rapidly. However, I often used Eowyn's ability to kill Ulchor's guards in the first round, ensuring that they didn't stick around to damage my heroes. Decide which Mordor card you don't want to see and ignore that stage. Make an order in your head, and start working on it. I liked to avoid the Tower of Barad-dur, and keep Under the Watchful Eye away for as long as possible. Covered in Darkness is one that you want to wait for until you've had the chance to play Elrond's counsel and a Galdhrim's Greeting.
Don't be afraid to sacrifice an ally and make the contract flip back, especially when Ulchor makes an appearance. Vilya and Steward means that you can probably replace a Bofur or an Azain with something better next turn. Keep an eye on what power of Mordor card will be revealed during stage 2, so you don't suffer any nasty surprises. Once you have survived the initial encounter with Ulchor, you should be able to power quest and survive a subsequent combat with him. Hope you'll enjoy the deck!