I think a delayed bounty system can solve the problem:
1. when you have done a minor crime, such as stealing, as long as you did it quietly no one will know (that's the way it is in Oblivion)
2. when you have done any crime outside a major city limit, as long as the guards aren't present during patrols and such, you are bounty free.
3. when you have killed someone in the city, as long as you did it quietly, you can walk away like you walked in without any trouble. However, the guards will start investigating the crime, they will find witnesses who have seen you around the area at the time of the crime, but since they didn't have Mac Taylor helping them, there's a chance that they won't ever catch you for the crime (granted, there is a probability that the guard will one day recognize you as the killer. just roll the dice).
4. If you have killed someone before and you kill another person again, the probability of being caught multiplies, because more evidence now points at you. And for each major crime you have committed, you are more and more likely to get caught.
How do you think about this idea?