There is definitely more that can be done.
I once suggested that the recidivism system be applied to comments where users were then prevented from commenting for certain periods of time based on the amount of comments they had deleted by moderation or flags.
I still think that is a good idea, however, from discussions with some of the other moderators and Community Managers here at Stack Exchange, the resounding response that I heard was "If a user cannot be trusted to comment politely, then they shouldn't have their comment ability removed, they should be suspended." So, that is what I would suggest here.
Either a comment ban or an actual timed suspension ("cooldown period") tied to some threshold for deleted comments (where the deletion was not the result of self deletion, post deletion, or from a system generated comment) which would require a Moderator to approve prior to being instated.
The Be Nice policy was a good start, now it needs enforcement.