Frood, resolving all the issues you said are difficult. But, as I said, AI is a challenge, and is making progress every day.
In videogame to have hard AI “players” usually they cheat. For example in Warcraft, Computer Players have advantages in collecting of money, so they are still stupid but have a lot of money and units!
The best AI I have ever found in a Videogame, that is alsofamous for this reason, was in “Carriers at War” produced by SSG. (By the way in the last weeks Matrix Games website announced the release of the new version of Carrier at War that seems great).
In that game the AI used some predefined strategy, that are casually selected and mixed up, and may also be changed to adapt to the game.
Indeed, I think that the real improvement in Videogame AI will be when the “Strong AI Model”, will be used. The difference with the ordinary used “Weak Model” is that the AI Learn, and so it may become better at the game, the more games are played. So you do not need to create a perfect AI at start but you need an AI able to learn. No one game that I know have this feature, however.