That kind of lookup seems like a great use case for a graph database. These kinds of queries are trivial and reasonably fast there.

I think where such a system would shine is in background banter. The player has to observe the NPCs telling each other these facts so he can appreciate it. That also opens the door for the player stepping in to prevent the spread of information. With the right setting that could be a major game mechanic