@Heaven UO had towns with guards and reputation (global, not per-town). Murderers just didn't go into down [sic], and ganked people when they left. How is this different?
Guards could roam the newbie areas, providing an "island" to run to if gankers were spotted. The caravans could be regular enough to provide safe passage between towns.
Additional creative options could be used as well...
Bounties? The more people of "good" reputation you gank, the higher the reward for bringing you down. This would promote "good" players to get together to hunt down the "bad" ones. The above mentioned anti-gank gank.
Hired guards? NPCs that accompany you for a period of time. Longer periods and more elite guards = higher pay. They would be defensive only, so you couldn't gank with them?
Incarceration? Maybe guards don't kill a player with a bad rep, they capture them. Screen goes black and the player wakes up in prison for a certain amount of time. If their reputation is bad enough...to the gallows with them! If not, they may be released outside of town or if they're borderline they may be given a warning and set free inside the town.
And of course there are options associated with death that may be attractive. Getting ganked as a nub isn't nearly as painful as getting ganked as a high level ganker. If there were some sort of penalty associated with dying...it could serve to curb the negative activity. I'm personally all in favor of perma-death (with caveats), but what if you just timed a dead character out based on what level they are? It would definitely introduce a level of risk management to ganking which is what its all about IMHO development wise. If you can introduce enough negatives into the equation you're going to cut back on people ganking other people.
I guess any developer needs to ask themselves: do I REALLY want to prevent newbie killing? I mean, if you WANT a "care bear" game world then sure, maybe its a fit for your project. But I think the process of coming up with ways to allow newbie killing with consequences will make your game tons better. More options = more gameplay = more fun!
Take care.
