I think the fact that strides have been made in the general area of dynamicizing certain actions (like simultaneously rendering mouth movements with spoken language in games) are steps toward that grand goal of games having AI that not only acts smart, but even has dynamic scripting, based on "observances" and other environmental stimuli. Also, hinted/dynamic animation is pretty unbelievable now. Just see how real it looks when a character is tackled in a Madden game.
I'm confident even the "hard" problems will be solved in the very near future.
That's a good point, and maybe I was too binary in my original statement-- there are a lot of parts of NPC design that are more physics simulation than AI. I'd still say there's a categorical distinction between "respond appropriately to being hit by a linebacker" and "respond appropriately to someone putting a bucket on your head", though. Like you say, we're close to realism on the former; much farther from the latter.
I'm confident even the "hard" problems will be solved in the very near future.