How about rather than down-voting, you allow people (possibly with some minimal karma) to delete comments if they violate the terms? If a comment is deleted, there would be a trace showing that there used to be a comment that got deleted by John. John's profile could then show all the comments he deleted, just like it now shows John's submissions and comments and anyone (perhaps with the same minimal karma) would be able to revive a frivolously deleted comment. Hopefully, that would mean that people would not delete comments unless they can stand for it.
But I'm pretty new to HN, so my comment may not take into account its evolution.