The only reason that I used the word random to describe this process is that you can't have it entirely determined by stats, otherwise you'll get the same outcome every time in any given situation, which kills replay.
That's true only where identical situations are likely. If enough factors are allowed to be dynamic, it's quite possible to have an entirely deterministic solution that'll never repeat in practice. Certainly you can't have everything determined by
static stats/factors if you want variety - but that's fine, since you'll be aiming to construct a world that's as responsive/dynamic as possible anyway.
For NPCs, all that's really necessary is to give them some autonomy, quite a few stats, and medium/long-term responses to their interactions. Bumping into an NPC with exactly the same attributes, skills, health, knowledge, mood, position, finances, desires... is never going to happen, so it couldn't matter less that a deterministic algorithm would select the same response in all such situations.
In any case, I'd say that the repetition problem you outline is exposing a more fundamental flaw: the problem isn't that the algorithm spits out repetitious results in identical situations; rather the problem is that you're allowing identical situations to occur at all. Two real situations are never going to be anywhere close to identical. If two of the situations in your game are considered identical by such an algorithm, it's either a particularly dull world or a needlessly blind algorithm.