These are the kinds of discussions that I like, so since this thread is kinda old, I will do a necro.
Here's my wall of text reply. Robert, think of this also as my two-cents for the game you're making, and for anyone else who's also making a game:
The thing to understand here is that the act of "finding out the one or two overpowering methods to win the game", that's a problem that any game can have, tactics-genre or not. You could say it's the bane of any game designer, unless he's designing the game to be like that on-purpose.
It reminds me of this game, Massive Assault, which is dressed up as a tactical war game, but the more you play it, you realize there's always only one best way to win each mission, and it pretty much devolves to a puzzle game. It was actually fun for a while, so I suppose some people actually don't mind that. I take it the mentioned Battle Isle is like that.
It's a natural inclination for us humans (in general) to, once we find a game that interests us, to always optimize our strategies. And once we finally exhaust all avenues, the game becomes boring, and we'd prefer to move on to the next interesting game. Everyone goes through this. This is what we experienced when we played tic-tac-toe as a kid.
What games will want to aim for is more breadth: giving the player numerous methods to win the game that are equally effective, it's just that designing a game like that is hard to pull off. In a word, variety.
----
There's also the issue of how much would you want the character building part (i.e. planning out of battle) to be more of an influence in winning battles as opposed to being clever on the battlefield and using actual tactics to win the game (i.e. planning in a battle).
So on one end, you'd have a "tactical" game where leveling-up and grinding is paramount (Disgaea comes to mind).
And on the other *extreme* end, you'd have a game where it was designed so that level 1 characters can win a fight against level 80 characters as long as the player was very good with tactics. Of course the point there is, why not just get rid of levels altogether? The problem there is that it sucks in that it doesn't feel like your character is "growing" after every victory.
For most of us, I don't think we'd really want a game that goes on either of those extreme ends, so you'd design the game where character management (leveling up, stat allocations, squad composition) is as important as being clever on the battlefield (proper positioning, using terrain to advantage, etc.).
----
Galrdred brings up a good point: fog of war will help stop battles turning into puzzle solving affairs. Risk management (e.g. "should I explore this part or not?"), "mind games" with your opponent, use of decoys, etc. are important parts and would make any tactics game more interesting.
----
Also an important point is whether you want your game to rely on "hard counters" (borrowing the term from Starcraft). Meaning to say e.g. fire-type damage always trumps water-type unit. Aka rock-paper-scissors system. Heavy use of that will obviously make the game a puzzle-solving experience. However, there are times when those things simply make sense (cavalry is weak against spearmen), so I wouldn't throw out the idea completely.
----
I think one aspect games can improve on is making terrain an important feature (advantage of higher ground, using tall grass for concealment, allowing units to create temporary bridges), and of course, interestingly designed maps.
Also, giving unit positioning and formations more emphasis.
Those things (terrain, positioning) are features that aren't inherently a "have only one way to be effective" type of system like a rock-paper-scissors system would be.
Because terrain is (generally) accessible to all units, and all units can be moved and positioned regardless of their level or class. This means a lot of permutations and combinations of things to try out in the battlefield. And not too much reliant on the character's level or class. This is, what we were aiming for in the first place: breadth, variety of options.
The restrictions would be more on the actual geometry, so properly designed maps are a must in these things.
But ultimately you still need to be mindful that your design doesn't devolve into a puzzle-solving experience.
----
Galdred's right, the good tactical games are the ones that do not "break" as soon as you get an unlucky roll. It's more of your skill as a tactician (and of your opponent's) that decides victory or defeat. I mean, the whole point is that it's a tactics game, right?