As Pluto and Lucevar have mentioned, certain information is saved in the savegame itself. If you have ever run Enchanted Editor, you have seen entries such as "NPCs Altered by Player". Basically, this means that everything in a Cell that your character has been in (whether you've touched it, talked to it, looked at it, or not) is "remembered" by the savegame.
As has been mentioned, if a new game looks fine and your saves are what look weird, you have three options:
1) Clean your save with WryeMash.
2) Take your character to a small, unmodded interior cell where there are no NPCs and wait or sleep for 72 game hours.
3) Clean your save more thoroughly with Enchanted Editor.
The first two should not do any damage to your game, WryeMash even backs up your save. I would think very hard about putting the NPCMP back in before doing the 3rd option. Using EE is kind of like editing your registry, if you back up your save and use it carefully, you can fix a lot of problems easily and completely. If you delete the wrong thing, you could make that file unplayable. But then again, you have a backup, so you can go back and experiment all you want!