i have been lvl 3 notorious, use stealth to get past guards
you must be aware of your surroundings, constantly looking for hiding places and escape routes incase of an emergency
tear down posters and bribe town cryers to rid yourself of noteriety
also i'm almost positive the amount of guards is the same in all three levels, they are however more aware of your presence and of who you are
you obviously have the tools and abilities to do these things with minor problems
you just need to change your strategy a little bit between regulars, officials, jagers, etc., and out in the frontier, travel by trees is my advice