Two more variations on the penalty system:
Have the penalty dependent on history, e.g. replies to a comment with -3 score are penalised only if the original commenter has negative karma over the last 30 days (or maybe if the commenter has total karma less than 10 or 50 etc.). (also suggested by shminux)
Use comment score to compute the penalty, so a comment with -2 only takes 2 karma to reply to, while one with -10 takes 10. (Obviously some other proportionality factor could be used, or even a different relationship between comment karma and reply penalty.) (ETA: Just thinking about it, this would encourage people to vote up before replying, so the penalty computation should probably ignore the reply author's vote.)
I like the proportionality idea but still want to be able to express a vote that says "I want less posts like this" without also saying "I don't want replies to this". My proposal is that replies to comments at -5 or better are free, and replies to other comments start at a score 5 better than the parent.
The recent implementation of a -5 karma penalty for replying to comments that are at -3 or below has clearly met with some disagreement and controversy. See http://lesswrong.com/r/discussion/lw/eb9/meta_karma_for_last_30_days/7aon . However, at the same time, it seems that Eliezer's observation that trolling and related problems have over time gotten worse here may be correct. It may be that this an inevitable consequence of growth, but it may be that it can be handled or reduced with some solution or set of solutions. I'm starting this discussion thread for people to propose possible solutions. To minimize anchoring bias and related problems, I'm not going to include my ideas in this header but in a comment below. People should think about the problem before reading proposed solutions (again to minimize anchoring issues).