One thing that we always joked about but have never done, is giving nasty people's names to a bunch of recruiters to help them to find a job someplace else.

More practical is making sure you have account management with relationships at a higher level to put a stop to the abuse.