I hired an entertainment attorney once. It didn't totally result in me getting my way, but the bleeding did stop, and the studio involved made a point of complaining that I'd taken it to that extreme (translated: they took notice).
You may not have to take it that far. If you keep your point simple and clear, and ramp it up a notch or two past the regional booker, you'll definitely get noticed. Break your goal into small bites, design those bites to end in tangible results, then use that to move on to the next goal. Also, pick a studio that's most likely to make a move before everyone else. Disney is one such. You get a clearance removed from one studio, or even shorten the clearance window, and most other studios will quickly follow.
The AG idea is good, but a last resort. Many studio contracts only mention clearances as something another theatre company has to request. Ask for documented evidence that a clearance was requested, then go after that company for anticompetitive practices. You could get your clearance lifted, and the studio saves face, making it work for all in the end... except maybe, for Carmike.
Aggressive booking also helps. Whether you book your own or hire it out, evaluating that part of the process would be a good idea. Personally, I wouldn't touch booking again with a 50 foot pole, but some exhibitors have a real talent for it.