We had our first win against The Siege of Cair Andros tonight, and I was pretty happy with how our decks performed. We tried 5 times with a different deck with no success, mostly perishing on stage 1. I retooled the decks with a different approach mind, and we did better immediately: 1st try got to stage 4, 2nd try had to quit due to a poor start (The Banks was immediately destroyed and Eleanor was killed by shadow effects), and we won on the 3rd try. Here are the deck lists, and below that a turn-by-turn of the game for anyone interested.

Deck 1: Tactics/Spirit

Hero (3)
Beregond (HON) x1
Eleanor (Core) x1
Glorfindel (FoS) x1

Ally (29)
Arwen Undomiel (TWitW) x3
Defender of Rammas (HON) x3
Gandalf (Core) x1
Northern Tracker (Core) x2
The Riddermark's Finest (THoEM) x3
Vassal of the Windlord (TDM) x3
Winged Guardian (THfG) x3
Eomund (CatC) x3
Gandalf (OHaUH) x2
Rider of the Mark (RtR) x3
Westfold Horse-Breaker (THfG) x3

Attachment (8)
Unexpected Courage (Core) x1
Light of Valinor (FoS) x3
Horn of Gondor (Core) x1
Ancient Mathom (AJtR) x3

Event (15)
A Test of Will (Core) x2
Elrond's Counsel (TWitW) x3
Feint (Core) x2
Hasty Stroke (Core) x2
Ride to Ruin (THoEM) x3
Dwarven Tomb (Core) x1
Strength of Will (Core) x2

Total cards: 52

Deck 2: Lore/Leadership

Hero (3)
Dain Ironfoot (RtM) x1
Ori (OHaUH) x1
Gloin (Core) x1

Ally (24)
Dori (OHaUH) x2
Erebor Hammersmith (Core) x2
Erebor Record Keeper (KD) x3
Fili (OHaUH) x2
Gandalf (Core) x3
Longbeard Elder (FoS) x3
Longbeard Map-Maker (CatC) x3
Miner of the Iron Hills (Core) x2
Snowbourn Scout (Core) x3
Kili (OHaUH) x1

Attachment (16)
Asfaloth (FoS) x3
Legacy of Durin (TWitW) x3
Steward of Gondor (Core) x2
Song of Wisdom (CatC) x2
Thror's Map (OHaUH) x2
Path of Need (FoS) x1
Healing Herbs (FoS) x3

Event (13)
Daeron's Runes (FoS) x3
Sneak Attack (Core) x2
Gildor's Counsel (THoEM) x3
Dawn Take You All (RtM) x3
Radagast's Cunning (Core) x2

Total cards: 53

Heroes were: Beregond, Eleanor, and Glorfindel (FoS) in deck 1; Dain, Gloin, and Ori in deck 2.

The idea was to quest hard and use extra tools to explore the Battleground locations as quickly as possible, then quest through the 5th stage without stopping for anything. I had a tactics/spirit deck with a lot of Rohan location-manipulating abilities. Feint was key for preventing attacks. My partner had a dwarf deck with some shadow effect removal, Thror's Map and Asfaloth for my Glorfindel. Gloin made cash and Healing Herbs off of Ori healed him right up. Steward of Gondor on Ori. Dain was essential for winning stage 5. Eleanor canceled a Southron Support at a key moment.

Turns looked something like this:
Turn 1: Thror's Map makes The Bank the active location. We failed to clear it, putting only 1 progress token down. Sneak Attack Gandalf to remove an enemy during the quest phase to do even that much.

Turn 2: Asfaloth comes out of Deck 2, goes on Glorfindel and finishes The Bank. Thror's Map makes The Approach the active location. Deck 1 played Arwen and a Winged Guardian. Steward of Gondor from Deck 2 goes on Ori. Ancient Mathom on The Banks gets three cards for Deck 1. We quest hard and clear The Approach. There's a Battering Ram in play, which we are forced to take undefended or Gloin, the only ready character. 7 damage on The Citadel.

Turn 3: Unexpected Courage on Beregond and Light of Valinor on Glorfindel for Deck 1. Deck 2 buys Gandalf to lower threat. Gandalf quests. We quest heavy and, as luck would have it, The Citadel is not destroyed. We put exactly 11 tokens on it (didn't need Asfaloth) and move directly to stage 5 because all Battleground locations are gone. Stage 5 will have the Battle keyword thanks to our 6 accumulated victory points. In tthe combat phase, we use Feint on the Battering Ram and also clear out two engaged enemies. There's a Harad archery guy in the staging area.

Turn 4: Deck 2 has got 5 dwarves by now and draws 2 cards. The Battle keyword is not good for us. Dain helps, but we just have more Defense power than anything else. At the end of this turn, there are 3 Harad archers, and we've only put 9 progress tokens down. Gloin is making money from the archers, and we spready the rest around. Deck 1 uses Feint on the Battering Ram. We clear out 1 or 2 more engaged enemies.

Turn 5: We quest all-in, anyone with any sort of attack power quests in the Battle. 2 Battering Rams come out -- it's a total of 10 threat vs. our combined 16 questing power, giving us exactly the 6 progress tokens needed to finish the quest. Every single sword was needed in that fight!

A good game, lucky encounter card draws and pretty good player card draws as well. Deck 1 was holding too many location-manipulating cards in the end (after the Battlegrounds are gone, they are pretty unnecessary). Final threat of 34 and 32 (or thereabouts).