Cartel members don't need to agree to not compete against each other, they simply need to agree to work together to restrict competition. In this case, incumbent taxi firms could be in cutthroat competition with each other, while still lobbying to prevent new entrants into the market.
I disagree that there is no way for customers to choose cabs which offer good service when street hailing. Sure, there is no way to provide 100% certainty that service will be good, but this is the case even under intense regulation. Considerations like reputation and the desire for future business do have a tremendous regulating effect. That doesn't mean they are perfect and I'm not saying there should be no regulation whatsoever, but I fail to see how restricting competition makes an already inefficient market more efficient.
I don't understand your argument re: choosing cabs. You have no idea what cab will pick you up when you hail one on the street, and you generally don't get to pick and choose given the circumstances. Thus, someone with a good reputation has no way to get more customers than someone with a bad reputation.
IME, and this probably varies from place to place, cab drivers sometimes will give you a business card after a ride, and you can then call then directly. I've worked places where we basically had one driver that was the go-to for the (small) office.
You might not get to pick the cab driver themselves, but you can pick the cab company you are willing to patronize (even more so where there is increased competition). If I have a terrible experience with Company X, I probably won't use them again unless they give me a good reason to change my mind. This is a powerful incentive for companies to ensure their drivers are providing a quality service (or at least it is in a competitive market).
Do you think people hailing a cab can effectively choose between different cab companies (there are dozens here in DC, for example, with different markings) at that instant?
I disagree that there is no way for customers to choose cabs which offer good service when street hailing. Sure, there is no way to provide 100% certainty that service will be good, but this is the case even under intense regulation. Considerations like reputation and the desire for future business do have a tremendous regulating effect. That doesn't mean they are perfect and I'm not saying there should be no regulation whatsoever, but I fail to see how restricting competition makes an already inefficient market more efficient.