Thats so true, the AI in Starcraft does the same cheating, to be competitive with the player. Total War is the same mess. A really adaptive and smart AI is in our time only a dream.
I still have many doubts if a fake AI .. as in programming every or the majority of her actions and reactions to the player is not preferable or will not result in a more difficult opponent, sometimes in some games there are so very specific actions that a behavior AI can't cope or will waste so much resources to consider them compared to just putting a single line of code prohibiting her to not do that action, not doing this makes usually makes her predictable and easy to exploit in those instances.
Sure, but isn't a fake AI much more predictable? well most games that used a fake AI are very predictable but I think this failure results from only start to work on the AI as an "afterthought" when you already advance in production... I think for a good "AI" you need to start by making a game around the AI and not the player.. this means mechanics and gameplay would be first put in her context. This would still mean the player would be the final consideration but everything would be depended on the AI.
As you can see even on HoI 4 the main consideration is accessibility, a better a more polish experience for the player and more immersion, A.I. is only mention on helping the player not by using the actual game mechanics and working against the player and it seems in HoI 4 A.I. was never the factor that rules them all, there hasn't been even a DD by the stage about A.I. nor Is A.I. ever mention on the 1st DD as a concrete and focus objective and that is worries cuz it wasn't that great on previous titles. I also find increasing the difficulty just by giving a bonus to A.I. battles cheap and insulting
Maybe the answer is not only starting with the AI in first place but also using a hybrid A.I system with behavior and specific programmed actions but being the latter more prevalent to not only save performance but because it's also easier to adapt to new gameplay and new mechanics.
I could be wrong maybe paradox as a surprise down her sleeve but honestly if they were proud and this was a major focus it would have already been mention.
The best or most challenging A.I. I have encounter was in Age of Empire 2.
http://ageofempires.wikia.com/wiki/Artificial_Intelligence
The AI was already a very good match in moderate difficulty(it actually kick my ass a few times) and it was efficient at playing the game maybe because it was scripted to just do what it matter to win but it work in providing a very good challenge, only getting artificial bonus on the last difficulty.