As far as crime and punishment goes, my opinion is that there are two main problems:
1: 6,000cr is peanuts for murder. Come on man. Add at least one zero to that, probably two.
2: Our law enforcement system is senile right now, it forgets far too easily.
I think we need a notoriety system. A criminal rep, if you will. When you do crimes, in addition to bounties you gain notoriety. Notoriety is still specific to the system (with some exceptions, we'll get to those), and it can decay but very slowly. They'll forget a parking ticket in a couple hours, they'll forget an unlawful interdiction in a day or two. Murder though? They'll hold that grudge for years.
Low notoriety doesn't really do anything, though you might find yourself getting scanned more often and find the police giving you the cold shoulder if you're starting to get enough to be considered a miscreant/petty criminal.
As you start to get toward the middle of the notoriety range, your notoriety starts to spread into nearby systems, systems roughly within the typical mission radius (so somewhere around 20 to 40LY) will start to hear of you "through the grapevine", and crimes committed in a system where you're notorious will raise your notoriety in all its neighbors too. Upper-class stations in high security systems where you're notorious will also start closing some station services to you, they don't want your business.
At high notoriety ranges, things get serious. You get exiled from the system: attempt to dock there, at least in a station not controlled by the pirate/anarchist faction, and you'll find the cops waiting for you on the landing pad. Your ship will be impounded, your character will be tried and executed. Whether this just costs the ship (no rebuy, insurance doesn't cover that) or wipes your save is up in the air, but either way the intent is this: if you are Billy the Kid levels of notorious, be very careful where you dock. Higher security systems will exile you faster than lower security systems, because they have a stick up their rear when it comes to that kind of thing. Systems where you're exiled will also never expire your bounties (ie bounties from that system are permanent until actually cashed in by a bounty hunter), and police in that system will give you a "trespassing" bounty every time they lay eyes on you. You made them angry.
A side effect of high notoriety is also that if you've gotten to that level of notoriety in a system, then all its neighbors are probably in the Medium range... which means your reputation is spreading to all *their* neighbors too.
It's not *all* bad though: notoriety will gain you favor with other pirates and criminals. Pirate-controlled stations will offer you better missions, or offer station services that normally aren't available (for example, a pirate shipyard at an outpost that normally doesn't have a shipyard). The expanded services are partially to make up for losing access to almost all big stations (though as long as you haven't been *too* naughty, you could just fly to a system where they haven't heard of you...).
Now, for the exceptions to it being local: committing crimes in a CG system will raise your notoriety in all systems, because events in that system are being broadcast on GalNet. Everyone will see them. Murdering a commander also carries a "bonus" global notoriety increase in addition to the normal local one. This is because the Pilot's Federation will hear about what you did.
Common criminals should be minimally affected by notoriety. The notoriety gain for getting caught smuggling is small and can be managed simply by not getting caught in the same system too many times in a row. Similarly, the notoriety gain for interdiction and assault are small compared to murder, so a pirate should find his notoriety manageable as long as he doesn't make a habit of killing his targets, and of course as long as he keeps on the move to let the heat cool down. If you decide to roleplay as a terrorist or serial killer though? Well first of all you've got some issues to work out, you should probably talk to a therapist about that, but more relevant to this discussion: the game will treat you like one.