please forgive me if i seem over simplistic in either my understanding or suggestion... but isn't the reason that the characters get out of hand is that the dm allows it?
i'd like to address many of the examples i've seen referenced, rather than any particular individual or situation.
it seems that in each case of characters running rampant is due to the fact that the natural consequences of the player/character actions are not being applied by the dm in question, be it deliberate or not on said dm's part. this can be for a variety of reasons some of which have already been mentioned. however, in some cases, it is perhaps because the players reject what the dm has decided are the natural consequences.
as i'm sure everyone is already aware of, these sort of social games assume cooperation and mutual understanding on the part of all participants. when one, some, or most do not agree, then the game falls apart, regardless of what one might try to do to fix it. diplomacy and the like requires discussion, resolution, and agreement in order to work.
to be honest, i don' t get the whole being evil thing. it simply does not appeal to me. i've mentioned before that evil=auto-npc in any of my campaigns, and i simply won't play with groups or players with evil pcs. this has resulted in dry-gaming spells years in length. some of my games are taking place over the phone or via pbp at a rate of one post every month or four, and one phone session a year or so, just so that i can play with the specific people in question. i'd rather play patiently with good people, than not play at all, or play with bad gamers.
d&d is a game of HEROic fantasy, after all. generally speaking, even by the designers, the assumption is that the players are the heroes.
getting back to the individual situation from the OP, it sounds like you've really tried hard, and there are just some seriously different goals.
i guess my comments are all pretty much stating the obvious and not much help. sorry.