I'm posting this thread because I'm wondering if anyone else is like me, where you see a hero that you're CERTAIN there's a good strategy / deck for using them, but everything you try ends up just being sub-optimal.

Celeborn -- Since I generally play "themed" decks, I'm having a really hard time coming up with a working deck synergy for him. All of the best Silvan allies so far have primarily been Lore (Mirkwood Runner, Mirkwood Tracker). Other than the Silverlode Archers, how does his special ability really help? Granted, he's got very good base stats . . . but I can't really think of any deck I'd use Celeborn with where I wouldn't rather just play Elrond instead. Every time I've played Celeborn, it's been with Elladan/Elrohir, or Loragorn/Beravor, and every time I keep thinking, "Yeah, would much rather have Glorfindel . . . or Elrond . . . or Legolas . . . or Bard the Bowman . . . "

Faramir -- Faramir is easily my favorite character from the books. And so I'd love to find a really viable deck concept with which to use him . . . but frankly, I'm struggling to do so. The Ithilien Ranger allies and traps are all good, and such, but his special ability is not particularly useful except for VERY specific quests (Tactics Boromir + Faramir is AWESOME for Shadow and Flame, for instance). For most of the good Gondor-themed decks, Faramir would be massively more useful as a Spirit hero than Lore (access to treachery and shadow cancellation, threat lowering, and Light the Beacons).

Any other heroes that based on their stats and abilities seem like they should rock, but in actual play end up being rather "meh"?

Faramir is hard to use, only seen a few decks really use him well. In MP its hard because even with low threat the enemies probably go to other players. Tracker1 made a solid solo deck with him. Traps are key.

Celeborn is in the upcoming cycle, and if you check the spoiler articles there are several new cards that work a Silvan Synergy, so he'll be very fun.

While I certainly agree with your assessment on Faramir that his stats and ability are almost counter-intuitive to the archetype he is meant for; I think the criticisms of Celeborn are absolutely ridiculous at this juncture. Mostly because, well, he hasn't even been released yet! That and we've only seen a handful of cards that is supposed to go with the new archetype he will be the center of. It's like bashing Elrond before seeing Vilya or talking about how poor leadership Boromir is before having any of the Gondor allies from HoN and AtS. It won't be fair to assess Celeborn and his place in her meta until FFG has released or at the very least revealed all of the support for her Silvan trait that they seem adamant about boosting with the upcoming APs.

To get back on track however, I'd like to throw the much maligned spirit Pippin to this this list. It is already well discussed on these forums how his ability is too restrictive while also more damaging then beneficial over the long run. Plus when BR came out it flipped the hobbit trait on its head (and made it much more playable) making spirit Pippin that much more of an outcast

Fatty Bolger is one of those heroes for me. I like that he can be used outside of a Hobbit deck, but I am just wondering what kind of deck he would be best for. Has anyone had great success with him outside of mono-Hobbit deck?

Perhaps a Ranger deck would work well with him...

Without reading other responses, I will say this. Celeborn will easily soon be one of the stronger heroes, and a Silvan deck strongest synergy one, I believe. The cards will come in the next cycle, mostly, I suppose. But just from what we have and what has been previewed. Silvan Refugee can quest for 3 willpower and 1 resource, and for just another card you can get it back with The Tree People and with some luck (and almost certainty in the future) you should have a different Silvan ally in play. Naith Guide is also a super great deal, 2 resources 2 willpower a hero not exhausting for a quest? But you will probably want a Lore and a Spirit hero together with Celeborn. Could Galadriel be one of those? I would not bet against it.

Faramir, yes, he is not easy to work with. I currently run him with Denethor and Gríma in a mono-Lore Ranger deck which is not bad for a support.

For me, I am rather having a very hard time fitting Théoden. All the Tactics heroes seem to be busy elsewhere than in questing, only Thalin seems like a very good fit for Théoden but since I prefer theme and synergies, these two do not work too well together.

Illeimmoen: We both concur on Celeborn quite full-heartidly

Theoden is much harder to implement smoothly. The dual decks I posted in the deck building forum takes advantage of his great stats quite successfully whoever giving him tools that maximize the action potential with all of his values

Yeah, it is obvious that some heroes are meant for coop, Bard and Brand, naturally, and Théoden seems just the case as well. His stats are really nice to start with, yes.