It seems like most true "Open Mic Nights" are at music stores or small clubs where the performers also tend to make up the paying audience. In that case, you have a bunch of musicians that understand what Open Mic Night means, and they'll deal with the worst of the lot.

One option I've seen work fairly well is to skip the "Open Mic" part and install a Jam Session instead. Have a (paid) guy host it, have a set or more or less regular performers, perhaps on the dinner and free beer plan (and you already know who'll work from past evenings), and make it the hosts' problem to allow people onstage a second time or not. It seems to generate a higher caliber of talent, because there's more pressure to live up to the guys onstage and it looks like less of a free-for-all.

It also deflects the blame of "I want to perform and they won't let me" on the host performer and away from the establishment. :)

But it's a different feel. I agree with Michael -- if you have folks paying for the entertainment, you really need to make sure the entertainment is worth the price tag.