I thought I'd share this deck, with which I have beaten all three Heirs of Numenor quests in Nightmare mode solo.

It is strongly thematic with just the addition of some eagles to the Gondor line-up.

Obviously Trained for War is absolutely essential to beating Peril in Pelargir stage 3 and Into Ithilien stage 3 (Celador never dies with this deck so you always end up on stage 3). For Cair Andros I followed the strategy of going all-out to clear the Banks turn 2, and thus will-power is not needed - so I subbed in 3 x Feint for Trained for War.

The biggest problem is of course threat control but that makes for very close and tense games.

Interestingly this deck finds all three scenarios easier in Nightmare than normal mode - because, I think, some of the worst threat-gaining treacheries (Collateral Damage, Watcher in the Wood) are removed for NM.