1. Immediately knowing what's going on and who to blame is both unrealistic and slightly boring. I want to be able to sneak around at night and secretly assassinate the king, or just steal goods from the stores at night without anyone knowing what just happened.
2. Obviously this can only avoid being game-breaking if there are more intelligent defenses; shopkeepers should either lock stuff up at night or towns in the affected civ should start locking their doors once they hear that there's a nightly thief/killer on the loose. The travel of information should be king here; any scrap of information traveling around should cause the residents to become more cautious, and the more often suspicious things happen after you arrive the more suspicious you look and the less helpful people are in future. Sneaking in general should also be harder to train (though legendary ambushers should still be able to do what they can do now).
3. Attempting to kill a town should lead to more intelligent responses by the citizenry; when the normal citizens see that you are effortlessly slaughtering people in their beds or guards during the day, they should not try to fight you as well unless they either have a weapon or are cornered. Likewise, they should also not attempt to go about their normal duties; they should instead try to run off the map. Guards and weaponmasters are a fine exception as their job is to protect the town, though perhaps depending on their skill and how effortlessly you are killing them, they may decide that living is the better part of valor and flee as well.
4. Escapees are not a throwaway gag; in the short-term you have less potential problems in getting the area all to yourself, especially if you manage to scare away guards, but in the long-term this ought to cause serious issues. What should happen ideally is that first, there should be a lot of them, and so while you might be able to run down some of them through encounters (I for one would find it quite interesting to get encounters on the map where I am the intended predator instead of the intended prey) you won't get all of them, which leads to the problem of survivors telling the other towns about you going about splitting people's heads in half and carving off limbs left and right like some kind of maniac. The upshot of this would be that you try to go to the next town over, and suddenly you find yourself looking at an army of marksmen and warriors ready to turn you into a fine red paste. Perhaps this would take some time to build up, but I certainly think that gathering an army to destroy a single madman would be appropriate what with the havoc a properly armed and armored adventurer can cause (as well as beating the army being a truly awesome feat to pull off successfully). This is of course entirely dependent on one of the bloats (standing, commandable, traveling armies) being finished, but one Hacky McHackerson way to do it would be to change the composition of nearby towns to feature more guards/weaponmasters and less ordinary townsfolk. If possible, causing said extra guards/weaponmasters to cluster, so that you can't take them on one-on-one as easily might not be a bad idea either.