No matter what, notoriety won't stop gankers (and IIRC being pledged to a powerplay power bypasses notoriety completely if killing another player who's pledged to a different power) and only inconveniences "lawful" players who occasionally commit coincidental manslaughter or get accidental notoriety in AXCZ-s when an NPC flies through their cooling beam and then is killed by the interceptor.
Right thing would be to get rid of notoriety completely and replace it with infamy that you raise by getting bounties whether you kill a clean ship/NPC or not (eg trespassing, attacking clean skimmers and surface defence turrets will increase your infamy). High infamy unlocks more "shady business" with factions and getting bounties in a system increases your reputation with the anarchy faction(s) in that system. High infamy makes system security more suspicious of you and you get frequently interdicted and scanned by them (and shot at when you're wanted in the system), to a point that you need to use the SCO drive to get anywhere in a high security system. This would also disrupt the gankers—they need to move around the system constantly to avoid being pulled every 10 seconds when camping at the main star in Shinrarta Dezhra.
Reach high enough infamy and you won't be able to do high paying legal missions, but you get to do some very lucrative high risk illegal ones. Illegal missions are on a separate "darknet" mission board from anonymous contacts—you still see which faction wants you to do the shady business, but it won't be asked by their public figurehead. Infamy will decay on its own over time, but much slower than notoriety and only at low levels. Maximum infamy is semi-permanent and can only be lowered by doing certain missions.
That would be my ideal C&P which incentivizes a criminal career—lucrative and interesting missions involving piracy, assassinations, espionage, sabotage. And as much it disincentivizes being just a random murderhobo—having high infamy makes getting around in medium security systems moderately inconvenient and in high security systems you need to be fast and plan your travel to try and minimize stop-and-scans.
On a side note, powerplay NPC-s should be more aggressive. I shouldn't be able to interdict a wanted enemy PP NPC without them starting to shoot me immediately no matter if I have a PP bounty on me or not. And PP NPC-s should interdict me—otherwise what's the point of wanted PP NPC-s flying around in my power's HQ system?