Wasn't there a death penalty mentioned in TOS? Was it for breaking General Order One?
Like Nebusj said, it was for breaking GO7 (contacting Talos IV) originally, and for breaking GO4 (never explained) in the final episode. (But that doesn't change the fact that we never heard of a
jail sentence that wasn't six months in length.

)
One might say that breaking of GO7 was no longer considered a serious crime after Kirk and pals sorted it all out with the Talosians in "The Menagerie". Or, more probably, that Starfleet decided it was no longer worth the while to punish people for contacting Talos, because the Talosians were shown perfectly capable of also perverting the minds of those Federation citizens who didn't attempt contact with the planet (after all, Kirk saw a fake Mendez in his shuttlecraft, lightyears away from Talos).
Since the death penalty for GO7 had been set in the aftermath of Pike's adventure and thus was a fairly recent thing, I see no problem in assuming that another, similar incident later prompted the adoption of death penalty for GO4. Those things might come and go on a really short notice.
Even the numbering doesn't IMHO create a chronological disparity. GO7 might have been something as generic as "Don't break Class A planetary quarantine", with Talos IV the only planet remaining in such quarantine at the time. So GO7 would still stand, but the punishment would have been changed. In turn, GO4 might have been something like "Don't mouth off to beings more evolved than you", and Kirk's experiences with the Organians drove home the point that this was a more serious issue than previously thought. So Starfleet upped the punishment.
In general, no pun intended, I can't see "General Orders" as the sort of micromanaging that would tell Starfleet personnel whether to approach a particular planet or not. Certainly not single-digit General Orders. They'd have to be broader guidelines, yet with specific implications.
As for Fajo continuing his old hijinks, I do think that the future criminal treatment system works as intended. We do not hear of any repeat offenders. Mudd never pimped another woman again, or pretended to own a ship. Yates never smuggled for the Maquis again. Garak didn't contemplate another genocide. Paris didn't rejoin the Maquis. And Quark didn't smuggle kemacite or anything like that again (regardless of whether his "Little Green Men" arrest ever led to a sentence or not).
As for murder being punishable by death, nothing of the sort was suggested in "The Conscience of the King" where Lenore Karidian was guilty of multiple homicide. Instead, we hear this:
McCoy: "She'll receive the best of care, Jim. She remembers nothing."
Either forced amnesia is part of the cure/punishment for murderers, or then a bout of amnesia helped Lenore escape the future equivalent of the electric chair - or then the Federation will give Lenore the best of care to make her remember,
then fry her for her crimes. But IMHO the implication here is that there is no death penalty for murder, either in civilian law or Starfleet regulations.
Speaking of the latter, neither Garth of Izar nor Ron Tracey seemed to be facing a death penalty for their acts of mass murder. If the insanity plea always works, and if murder always is insanity, then it doesn't much matter whether there's a death penalty in the books, now does it?
Timo Saloniemi