I think perceptions of both how much it hurts and how prevalant such behavior is are quite dependant upon the person looking at it. -40 hurts a lot at level 2, and a lot less at level 6. It's hard to say how common this really is; if it hasn't happened to you, you may think it doesn't happen much, whereas if it has happened to you, you may feel that it is common. I come from the perspective of someone that this hasn't happened to, so my opinions may be tainted by that.
I am probably most in favor of the second suggestion, because I feel that technical solutions will fail. Having it take twice as long to vote down someone doesn't mean it won't happen (it just means, to the cynical, that you can have two vendettas at a time). I can also think of valid reasons for voting many posts by the same person down in a row. It's a way of dealing with a troll, for example, as nodes with too low reputation may be removed.
Likewise, I do not think the third idea will work; it's easy to circumvent. It would be simple to -- one or two nodes by someone a day.
Solution four would make the problem worse, perhaps even triggering new vendettas when a post is voted down without malicious intent. Not everyone is as gracious as lindex when it comes to accepting other people's votes. I am pretty certain that you already considered this since it is near the bottom of the list.
In the end, it always depends on the users. It's possible to limit the potential for abuse, but it cannot be completely eliminated in a technical way (without implementing meaningless restrictions, such as removing the option of a -- vote). That is why I think a discussion is better than any of the technical solutions.
I reserve the right to support another solution if one is suggested that I think is better :)
In reply to (kudra: people, not technology, best solve problems like this) RE: RE: (2): Limit on voting down a person (Run in circles, scream and shout)