(This review is no longer accurate as of FAQ 1.9)
A deceptively powerful hero. In wrapping The Line Unbroken for the Against the Shadow cycle I picked out Caldara as both one of my favourite heroes and one of the most difficult cards to use well. I would have also placed her in the 'most under-rated' category had it not been for the sizeable uptick in Caldara interest following the release of Sword-thain. Of course now, with Prince Imrahil as well, she's reached ridiculous levels where many people will tell you she represents one of the absolute top most powerful deck archetypes in the game, and I find it difficult to argue with them. Just Sword-thain made it ridiculous enough.
So let's get back to the categories I did put her in, favourite hero and difficult to use. One of the most significant reasons for both those things is that playing with Caldara requires somewhat of a shift in mindset and strategy compared to most decks. That's the big reason why a lot of people didn't use her for ages (and why a lot of people probably still don't), because they couldn't wrap their heads around how a Caldara deck works. Once you do get it, the actual building of it can be somewhat formulaic, but then a fair amount of variety comes out again in the correct piloting of the deck. I myself struggled with it for a while, attempting to put decent Caldara decks together but failing until I tried again with Galadriel and her Mirror, and also figured I'd just go pretty all out on the discard strategy, which you kind of need to do.
Alright, enough talking around the issue, so what is it about Caldara decks that gets so interesting and weird? Well, her ability involves discarding her, so for starters any attempt to make consistent use of it will involve using Fortune or Fate, a card which under any other circumstances is pretty much never used. This also means that while you're getting allies for free by discarding your hero, that's effectively off-set at least partially by the cost of Fortune or Fate to bring Caldara back afterwards. And saving up for FoF can be difficult, especially when you're down a hero and thus generating one less resource per round. All this adds up to make Caldara seem problematic at best, but bear with me here. Obviously a means of generating some extra resources is key to Caldara if you want to be triggering her repeatedly and consistently. The other significant point is getting allies into the discard pile for her to revive. This can of course be achieved by allies actually dying or being discarded from in play, but that makes it somewhat on the slow side as you have to draw and play the allies, and have them die, before you can bring them back with Caldara. The more efficient option is to use Caldara as effective cost reduction by discarding those allies either from your hand or directly from your deck. This immediately suggests some of the great combos with Caldara - Éowyn obviously provides a means of discarding from hand in addition to her usual incredibly helpful , but the real stand-out at the time of Caldara's release was the Imladris Stargazer/Zigil Miner combo, which lets you simultaneously discard cards which are hopefully allies to be revived, and also gain resources with which to play Fortune or Fate; and more recently the hero version of Arwen Undómiel does the same thing with discarding from hand.
Other possibilities include Frodo Baggins for access to cost reduction from Good Meal, Círdan the Shipwright for more discarding and potentially use of Narya to get more use out of the powerful allies, and my above mentioned liking for Galadriel and the Mirror, letting you find cards you want and also get things in the discard pile (most of which you don't really care that much about losing). Galadriel also gets you an extra action out of each ally and some more card draw. Finally of course I mentioned further up Sword-thain and ally Imrahil. Given that my Caldara deck was already a go-to choice for trying to beat Nightmare quests even before Sword-thain was released, and both Sword-thain and Imrahil make her more powerful, she's frankly ridiculous now. In a similar vein you can do some shenanigans with another player using Desperate Alliance to pass you another hero right before you discard Caldara, but that's obviously less consistent and requires co-operative deckbuilding. I'd just like to get briefly into why Imrahil is so amazing here as well, because while Sword-thain and Desperate Alliance shenanigans also net you an extra ally for each Caldara use, he would be amazing for Caldara even if he didn't count as a hero until after you resolved her ability - because he erases her downside. Usually if you discard Caldara and don't have the resources for FoF right away you're going to be short one resource every subsequent resource phase until you do bring her back. But with Imrahil, that's no longer a concern because he will generate resources instead (just make sure you spend from him first, as you do with Caldara while she's in play).
Not convinced yet? Because there are a few incidental benefits to Caldara which shouldn't be underestimated. It effectively functions as a kind of healing - put archery or other direct damage on Caldara, discard her, FoF brings her back on full HP. It works as condition removal if you put a condition treachery on her. It can be readying if she exhausts (probably to quest), then you discard her and bring her back again ready to maybe defend a weak enemy. A similar principle can apply to allies which die or are discarded. When you discard Caldara, they reap the same benefits of being fully healed and readied. In general the knowledge that pretty much anything which lands in your discard pile can be brought back again is incredibly liberating and allows you to shrug off effects which could be awful for other decks.
For further ideas of cards that slot nicely into a Caldara deck I'm going to point you at mine, for all that it needs some more updating: ringsdb.com Caldara is almost certainly the most efficient means of bringing in multiple Northern Trackers, and any other high cost ally is automatically a solid consideration (such as Elfhelm or more recently Glorfindel. With the advent of Sword-thain and ally Imrahil you get more bang for your buck each time Caldara goes, which makes it more feasible to use her to recycle allies that discard themselves, like say The Riddermark's Finest if you're worried about locations or Escort from Edoras if you feel you don't have enough (Ethir Swordsmen also work for Caldara, but I hate Outlands). The other thing they've done is open up the design space of potentially having Caldara still work even outside of mono-. I haven't tried it yet myself, but enough people whose opinions I trust have said it works that I can readily believe it.
So while Caldara may not look that impressive at first glance, don't be fooled. She's amazing if you're willing to get into that mindset and give her a chance. Anyone who enjoys tricksy plays should try Caldara at least once. My final point I'll bring up is the simple maths of it. I've had games where I triggered Caldara on average once per round for 5 rounds. After that I slowed down, but then I'd mustered 10 powerful allies and was well in control of the quest. Name me another hero that can muster that kind of ally army. Go on, I'll just beat some more quests while you're thinking about it. :P