I decided to do little experiment and try how many attempts I will need to win 5 times with deck, also using progressive play, so only the cards, which were available at that time, when scenario was out. This is #14: The Redhorn Gate.
Because of the bad review on Bilbo Baggins, I decided to build deck around him for this quest, just to try, if he can be useful and combined it with Rohan cards. I think it works quite well, if you'll survive first two rounds of the game. It also works good, because objective card ally Arwen gives you together with Théodred two resources on every quest stage and Bilbo gives you two cards per round. So you can build your party quite quickly.
Bilbo is the main character here and most of the attachments are for him: Steward of Gondor, Song of Kings, Song of Travel, both Dúnedain Warning, Boots from Erebor, Fast Hitch and A Burning Brand. You can also use Protector of Lórien on him on early stage of the game, howeverer, if you got it later, use it on Théodred who also get Unexpected Courage and both Dúnedain Mark. The amount of incoming resources let you play even the expensive cards quite soon.
The songs in combination with Good Meal let you play easily also cards like We Do Not Sleep and Grim Resolve and Second Breakfast will bring Good Meal back to hand if needed.
I won 5 games in 10 attempts, which is solid however I never read scenario's cards before I start to play it, so if I would, I think, the final number would be even smaller. Very nice adventure.