I agree with you that if the illusion of AI works, it's nothing to complain about. But you said "the illusion sometimes breaks" where I had a total different experience. I found the illusion breaking more often than not.
As for games standing out AI wise: Gothic 1 was a freaking breakthrough. The AI in that game is still better than most games today. Another game with rather impressive combat AI was Severance: Blade of Darkness. While fighting multiple enemies, the fuckers strafing towards your flank and back were really frustrating.. in a good way.
I think there is a
HUUUUUUUUUUGE amount of room for improvement in FPS AI. Enemies can be way more effective behind cover and fight against you in harmony. Groups A could pin you down badly while Group B storms toward you to zerg you... just to throw an example out there. I think I could leave it at that and still make my point.
Truly impressive AI is literally a hundred times better than the illusion of it.
Playing: Skyrim, World of Warcraft.
Future: Dead Space 3.