I have only ever played one game where it was possible to face insurmountable odds to win w/o the AI cheating, and that was Moo3 (Master of Orion 3, patched version of course). In that game, I recall being trapped in an 8-system neck of the woods with one big empire in my way. No matter what I did, if I went to war, I lost. Any other game I've ever played, there was always some tactic or method you could use to win unless the odds were ridiculous, or the AI cheated. Thus I'm not particularly upset that BI is winnable regardless of initial situation using certain strategies.

I suggest what others in this thread have suggested: Limit yourself in some way to make the game interesting. Way back when, when Doom I/II was the In game, I found it all too easy to beat levels using regular tactics, even on the hardest difficulty levels. Thus I started trying some variations, like only using pistol/fists, or completing nine levels in a row w/o save/load, etc. Suddenly the game became fun again.

Sometimes there are simple things a game dev team can do to make a game more challenging w/o sacrificing the fun factor (remember: frustration is *not* fun, repeat after me all prospective game designers!). But we must not always rely upon the devs to solve our gameplay problems for us. If slash'n'burn tactics make the game too easy, don't do them (many strategy games can be won this way, just go in and decimate the production pipeline of the AI). If blitzkrieg makes it too easy, don't. In Vanilla RTW, I remember once playing as Parthians. I took over what is currently modern day Turkey and Egypt, then waited 50 turns to let the Romans build up (so I fought their best armies possible instead of wimpy pushover units). In my last Carthage campaign, I deliberately chose not to take over Sicily and the Italian Penninsula to give the Romans a chance (easy win for Carthage: Take Italy in the first 50 turns before they can build up their empire or tech base).

My point is don't bother waiting for the Devs to solve all your gameplay issues. A lot of them are very very difficult to solve and don't yield all that much bang for the buck (you and a few others might be happy with feature X, Y or Z, but most will never notice). Some of them are not. But I've been waiting 20 years for a "better" game like you're talking about and have found it only once (Moo3 again, post patch). Learn from my experience and don't bother trying to change the world. Find your own challenges. Why do people restore cars, when they could "blitzkrieg" and buy a new one? Why do people run a marathon when driving a car is so much easier? Why do people play RTW with self-imposed restrictions when playing with the "best" tactics/strategy would be so much easier?