For quite some time I was reluctant to post again on the site, indeed I have other things to do, including playing (and especially deck-building for) the game. Yesterday I had a great deck-building session with some real fun quest testing. Together with what I have read recently, I will say this:
Build theme decks. For me, this is by far the best way to enjoy the game. Do not build a deck with a quest in mind, you would be selling yourself short, at least this is where my experience of some three years have brought me. It is much more interesting to restrict yourself when deck-building, like never putting Steward of Gondor into an Elven deck, or Unexpected Courage anywhere for that matter.
Of course, when you do this, you will not have one deck to rule them all but what is the point of that? Build several decks instead and then take one (or more, depending on preference) against a quest, and a different one (or more) against another. If you haven't tried this approach, I most strongly recommend it.
Some final thoughts: do not use a certain card, say a Test of Will, in more than a single deck. You can still win without it, the card pool is getting there. Also, do not worry that a deck is lacking in certain areas, like card draw. I used to be paranoid when a deck did not draw a lot, yesterday I was cruising certain hard quests with two decks none of which had a heavy draw; the card pool is really getting there...