This question is more on "feel" of decks, rather than actual deck construction. If I may, I would like to make an analogy to Magic, since I know that game very well.

In any giver color you play, there a a few different ways to make that color effective. I could make a Black deck that uses a "sacrifice mechanic" to power my abilities, "life steal" to maintain a good life gap, "graveyard recursion" to stay on top of my opponents creatures, or "discard" to limit my opponents spellcasting options. Any or all of these options can make for a very playable black that will win, and when combined with other colors, deckbuilding potential is almost limitless.

So far in AGoT, I have noticed that each House is more "Specialized." For instance, I can't imagine any House Targ deck working well without dragon cards to reduce STR and kill opposing characters. House Baratheon seems more suited to a power-rush with renown. Lannister seems to thrive on card control (kneeling and discarding).

So now I get to the actual question: Can decks be made drastically different from eachother within the same house, and still be playable? How much diversity has everyone seen in each house, and how often does it work well? If I go to a tournament, will the top Martell Players all be running House Dayne decks, or do other themes stand a chance? This has been brought up by players in my group who don't want to "pigeon-hole" a House into making a specific deck that works, and only that deck wil work.

(Note: My assumptions are based on a limited amount of gameplay, and I really hope to be told that I am wrong on this matter. I want to fall in love with this game, and I am almost there. The final piece that will send me into complete infatuation is the dynamic options for deckbuilding that exist in magic. I am only looking for hope here.)

There are weak themes and strong themes in each House, and as I'm sure you've noticed, each has a specialty, be it burn or kneel or power rush. As a result of this major theme in each House, some similarity between decks is bound to exist. At a tournament I would expect that you would see a number of Targ decks running some sort of burn deck, a number of Lannister decks running some sort of kneel deck, etc. There are obviously some cards that will be used in every deck of the same type; you're not likely to see a burn deck without Forever Burning, you're not likely to see a kneel deck without either Castellan or Alchemists' GH. There are also some cards that you would expect in every deck for a given House, regardless of the theme (Venomous Blade before it was restricted, and I would still bet on it being in most Martell decks now).
IMHO, how much difference there is between decks will partially depend on how strong the subthemes for each House are and how much diversity is possible while keeping a deck competitive; some Houses are better filled out than others. So as far as diversity goes, Stark can run a House Tully deck, a Robb + armies deck, a Direwolf deck, can use Siege or not, etc, but they are all military themed because that is what Star does . Targ can do Shadows, Cities, KotHH, and as a recent tourney winner proved, Dragons, but all have the burn theme. Trying to build outside of the "archtype" for each House will likely result in a less efficient deck - you might love the idea of a Targ military deck, you may even be able to build one that works really well, but it probably won't fare as well as a Stark military deck.

Generally houses have a theme but that isn't the only way they can win. Using your example, Targ is very successful with burn but there are multiple ways to build a burn deck and they still have other options which don't center on the burn.

Current Targ general builds which, while not all being championship quality, could definately hold their own:

Dothraki Military

Targ Burn (shadows and non-shadows variety)

Targ Summer

(soon) Dragon

Take a look at the submitted decks section at CardGameDB . There are tons of variety of decks there with each house having a number of different deck styles that can be successful.

As far as I see there is a very good amount of in house versatility possible right now.

If you take stark for example, they can use their military for a quick rush, or for board dominaton and you will be surprised how different both decks can be, regarding playstyle and cards used. And then there is the Direwolves deck, wich also having different flavors can range up to slow ultra board control. They also have a very well done Bolton theme wich can simply combine with all types or be a deck on its own featuring some witty combinations.

Beyond this, There is a good amount of resource denial/ location control possible in Stark, which you can use as support or as the driving deck strategy.

And this are just the major builds in my opinion.

Another example would be Baratheon. Yes it is very good at rush decks, but the house has a greater range. The shadow and Ashai mechanics blend together very nicely in a few different ways allowing Lanister-like powerfull board and even brutal hand control, and depending on your design focus can still utilise the quick power gaining ability, resulting in the "late rush" deck. There is also a Stark like location/ resource hate available up to the point of being the main focus.

And just to mention an exotic build that performs incredibly well: Baratheon threaty with the Isles utilising the plot Fear of Winter , is just cheap, fast and annoing. Well... and risky, too.

In general most decks do not have to dedicate themselves to a theme entirely, but choose wich in house theme to include to what extent in order to create the desired effect and pace.

Like in Targaryen you can use the same burn effects to clear the board, possibly repeatedly, at late game, or to "increase" your military claim in an agressive build.