Inspired by Mementix' mention of a mono-tactics deck I built my own. After some tweaks and changes the deck performs very well and won the last six games in a row. With this deck solving the riddles becomes fairly easy while it still provides enough WP to make some progress in the quest phase, with Legolas as a backup when too many locations pop up. Beorn is able to hold off some of the Goblins and can even be revived by Landroval.
It's important that at least one 2 WP ally is in the players starting hand, preferably Bofur and/or Radagast. In most of my games I lost the first quest phase and had to raise my threat up to 5 points. However, with one exception I managed to end the adventure before my threat reached 50 points.
The stats below should help to choose the right options to answer a riddle. Of course a player should keep a close eye on those cards that go into his discard pile, as the probabilities will change during the game.
Heroes: Beorn (12), Brand (10), Legolas (9)
Starting Threat: 31
Neutral:
3x Gandalf (core) (5 cost)
3x Radagast (5)
Tactics:
Allies
3x Landroval (5)
3x Eagles of the Misty Mountains (4)
3x Descendant of Throrondor (4)
3x Beroning Beekeper (4)
3x Veteran of Nanduhiron (4)
3x Bofur (3)
3x Winged Guardian (2)
2x Watcher of the Bruinen (2)
3x Vasall of the Windlord (1)
Attachments:
3x Rivendell Blade (1)
2x Blade of Gondolin (1)
2x Song of Mocking (1)
Events:
3x Hands on the Bow (1)
2x Feint (1)
3x The Eagles are Coming (0)
3x Goblin-Cleaver (0)
Deck stats:
32x Allies (64%)
7x Attachments (14%)
11x Events (22%)
9x 5-cost (18%)
12x 4-cost (24%)
3x 3-cost (6%)
5x 2-cost (10%)
15x 1-cost (30%)
6x 0-cost (12%)
44x Tactics (88%)
6x Neutral (12%)