I think every NPC should know at least the same kind of background information as each player creates with his or her character, e.g. who their parents are, where/when they were born, how old they are, if they are married, which god they follow, etc. (For example, I was very surprised to discover how few NPCs could answer the prompt "Tell me about Talad".) Also, every NPC should give coherent responses to questions like "Where are we?" or "Where am I?" which can be followed up with "Tell me about this place."
EDIT: After spending quite a long time scouring Hyldaa for a particular NPC, running from one NPC to the next asking them to tell me about her, it became clear to me that some kind of network needs to exist between NPCs regarding other NPCs. I know that some of them are well networked, but others are not. In this case, none of the guards knew anything about a NPC they would theoretically have to deal with on a fairly regular basis, namely, Finara Plund.
Could there be some kind of '3 degrees of separation' for NPCs? Every NPC who is in the general area of other NPCs should know those NPCs or at least give some kind of hint regarding their possible whereabouts. For an NPC in East Hydlaa, they might not know all the NPCs in Central Hydlaa, but they should know whether or not they know a particular NPC. It would be very helpful to get a response like: "I'm sorry. I think I've heard that name a few times, but not in this neighbourhood/district. Try looking in X."