I have a couple of suggestions:
 
1. Document, document, document. We use our internal ticketing
system to document carrier issues, and actually have a "customer"
created for each of our circuits, so that the history is readily available
on a circuit-by-circuit basis.
 
2. Call trouble tickets in for everything, and record the ticket numbers.
Follow up, get names, etc. All the stuff we know we should do, but often
times forget to do in the heat of the moment.
 
3. Pay all of your bill except for the disputed portion. Include with every
payment a "SLA CREDIT REQUEST" form that you complete, detailing
the reasons why you feel you are owed a credit, including the ticket
history, etc. Then, every month, include that documentation, and
copies of all other correspondence you've sent... until it is resolved.
 
4. Don't hesitate to escalate your issues up the chain. A simple:
"I'm getting no where with you and need to speed to someone more
senior" sometimes works. I've also used, with varying degrees of
success, "Let's get someone higher up than you on the phone, because
I doubt you're paid enough to deal with the crap I'm about to dish out."
 
5. If they're reasonably close (and this has worked wonders for me!),
gather up all your documentation, and take a day trip to their office.
It is pretty hard to ignore you when you're sitting in their lobby.
 
6. If all else fails, sue them. We did this very successfully against
MCI, got a TRO, then an injunction, and finally reached a settlement
that included the credits we were due as well as a cash payment
because of our grief and aggravation.
 
Best of luck,
--tlf