An important element in a larger world is that the stories continue to proceed.
Even when the main player is not actually present at a specific location to move them forward.

E.g. you have said something nasty to a girl who did not like that.
The next day her friend is also angry with you because of this.
So apparently they have "talked" about this together.

This requires that the characters in the world are also actively interacting with each other, creating a whole new dynamic to the game.
In general it will require a Level of Detail in the stories. The girls did not actually meet in the background, but the engine simulates as if they did.

Sounds like a great idea. Reminds me of Skyrim's quest tree, which had issues here and there, but was also sufficiently complicated. Adding player consequences is also what made it so great, and something more games should strive for.

As far as the implementation goes, how might this work? Only thing that comes to me at the moment is a giant Truth Table or State Tree...

Although the way you described it seems to include specific events that the NPCs would gain knowledge of, which would lead to many branching paths, and hence some pretty complex storyboarding. Would this apply to just the scripted stories or more generically ?

Maybe add more examples? just thinking out loud....

PC (fill in the blank) girl A =
girl A tells girl B
girl B no longer provides Option 1
PC now has a harder path to work with
Moods of Girl A, B have changed

PC (fill in the blank) girl A =
girl A tells girl B
girl B now provides Option 1 to PC
girl A now has Option 2 available
Moods of Girl A, B have changed

Overly simple, but trying to think generically, would it be any more complicated than a choices/options/consequences tree branch? If so, what is it specifically that would be different?

We currently working with state machines, but they have a lot of limitations.

We want to use actions that have pre and post conditions. If the pre conditions are met the character can use that action and the result is the post condition.

A simple example would be:

Basically above set of actions will result in this behavior.
There is no sequence in the actions, the characters try to put the pieces in a certain order to achieve a desired state.
A desired state in this case would be: I feel relieved.

So the individual actions are very simple but lead to a complex behavior.
This is how we want the new engine to work. Simple actions that lead to complex behavior.