Bitly seems to be the default in these discussions and it's clearly the market leader, but there are other companies to consider. I think even starting discussions with another company would force Bitly's asking price down considerably. They may talk about how Twitter is _only_ 30% to 40%* of their traffic, but no business wants to lose those kind of numbers.
* http://www.businessinsider.com/google-and-twitter-wanted-to-...