Very difficult to answer. Worms AI doesn't count, since making a skill shot is just a a very simple vector and force calculation (something that a pocket calculator could do in an instant). Actually a mark for the AI in the worms series is how BADLY they shoot, since the game has to calculate a reasonable random error chance depending on the skill level chosen. That being said, I haven't always found the AI's tactical decisions (and that's where it can be considered AI) to be particularly good. F.E.A.R. 3 has some good enemy AI, they move, flank, try to avoid dangers, retreat, and generally make life difficult for you without pulling computational dick moves like 100% perfect aim and reflexes over any distance. Something like that is easy for the AI. Technically any shooter could be next to impossible if the enemies were tweaked to be as efficient as they could be, since that would mean 100% headshots with instant reaction time. Not fun.
Starcraft 2 is also kinda average as far as the AI is involved: It gets some + points for good(not great) pathfinding (play stuff like C&C Generals, and you'll see why pathfinding can be an issue if it's retarded) but the actual AI opponents seem to be fairly predictable and again, mostly use computational dick moves. In this case perfect Macro and close to perfect micro. Also on the highest difficulty setting the AI actually CHEATS. It gets 50% (I think, might be less or more) extra income. So instead of one SCV bringing in 5 minerals per harvest, it gets like 7.
Some nice AI in a strategy game I've found in Shogun2. It seems to be able to use terrain to it's advantage to a perverse degree, generally manages units very well, doesn't seem to pull computational dick moves, and only very rarely does it do something retarded (like march his entire massive army one unit at a time at my firing archers)
It's also pretty hard to really define AI in a game (since the actual term is wrong, there is no "intelligence" only a set of programmed responses. it really boils down to how clever these responses are). You could argue that Gothic2 had some impressive AI, with all the villagers going about their daily business, chatting about stuff that happened around them, having a realistic day/night activity cycle, but that was all down to the ridiculous amount of scripts the devs wrote in. On the other hand we have Oblivion that tried to do the exact same thing, but without the ludicrous number of scripted events, rather with an adaptive engine (that would technically be much closer to "AI" than the gothic solution). Problem was, it was nowhere near good enough and in the end it felt like crap.
Half-Life 1 had some very clever AI back in the day, it was probably the first FPS where enemies tried to do more than charge you head on. Soldiers tried to use flanking tactics against you, would retreat and regroup, tried to flush you out with grenades, tried to ambush you. Even more interesting was that different enemies had different AI behaviors. Zombies were mindless and would just come straight at you, Headcrabs sometimes hid, houndeyes would try to stick in a pack, run away and regroup after casualties. Considering this was all in the age of Quake, it made for some impressive stuff, even if it would be only above-average today.
Thief 2 also had some pretty fun programmed responses depending on the difficulty setting. On easy guards would ignore pretty much everything except a body or a direct sighting. On hard however, an open door, an extinguished torch, a missing item, or even a drop of blood would send them on alert and looking for you. Again, not much actual "AI" involved, but very inventive stuff at that time all the same that hinted strongly at "AI" and made for a gameplay experience that could match very clever "AI"
Well, I guess I haven't really been answering the question posted and sort of more mused on different approaches to AI... but since there is no real "AI" in games so far, and such I can't pick the best one, I'll stick to my answer.