In my experience, affirmed by reading this thread, 3 distinct types of game AI behavior can be separated out:
1. Behavior based on a daily/monthly/etc. cycle.
2. Behavior based on/triggered by PC arrival/action/etc.
3. Behavior during battle.
While each of these can take many forms and soar to new heights of 'realism', I'd like to add another vote for not wasting time on any behavior that's not made part of a player goal.
In my world, some talented builders used mob scripts in the 90's to creatively incorporate #1 and #2 into some mid- and high-level zones. Daily cycles make certain mobs vulnerable/accessible in a restricted but predictable way. Triggers, of course, make sure that the little stage-play only unfolds when there are human eyes watching (no trees falling in an empty forest).
As for #3 (battle behavior), stock DIKU has mob memory and hunting mobiles that can cross the whole world, regardless of size, if you let them. With stock support for customized attack messages, some builders have done a good job of giving their bosses "special" attacks. In a few instances, special procedures for mobs were added to manipulate the environment in a super-magical sort of way (opening passages between rooms, melting or changing items players carry, whatever else can't be done in script)
I know there are levels beyond and above that, but unless you're talking turn-based, who can really absorb more than that in real time? To put things in perspective, MUDs are already impossibly hard for most people. And even turn-based games with advanced AI like the Civilization series just throw CPU cycles and increasingly complex relational databases at our (let's face it) nerdy selves, not "texture" or "lifelike" behaviors. It's not an accident that when most people hear AI, they think "Deep Blue" and not "the Mayor of Midgaard who can have an impromptu conversation about the medicinal qualities of unicorn dust." It's the state of the technology. Sure, I can waste a lifetime coding unicorn dust conversations only to find that some players really want to talk about fairy dust. And most players, of course, don't really want to talk at all.
On a final note, I believe a lot more in a lot less time can be accomplished by simple trickery. The player doesn't know or care what happens in the magical city when they're not there. But if they get there and someone tells them "You're too late!" and if, while leaving, someone tells them "We'll never forget what you did!" then they'll feel like the city has a life of its own, before and after them. Illusion is cheap, and effective. I think that's because people come to a game expecting to be tricked. While trickery is part of entertainment, reproducing the complexities of their mundane world, in all its hunger and pee, is not--it's what they're running away from.