Do away with the mechanic altogether
We're having this discussion in our group now and I've come to the conclusion that it would be easier to do away with the mechanic altogether.
Every NPC that accompanies the party should be there because they were hired or because of roleplaying reasons appropriate to the campaign. Here's why...
* Payment of cohorts is too tricky an issue. With the current rules, everyone at the table pays for one PC's choice of feat. If the NPC was a hireling that benefitted the entire party, then it makes more sense for the entire party to pay for it on the up-and-up rather than paying an individual PC extra treasure and magic items.
* However, if the whole party doesn't pay for the cohort, then maintenance (in magic items, etc.) for the cohort has to come out of the PC who took the feat--which unfairly burdens the PC and slows the PC's own progress for doing something that benefits the whole party (that being getting an extra hand to help the party). But, using that argument, shouldn't every PC get more shares based on the feats they choose? No, they shouldn't, which makes Leadership inherently unfair for the PC and the party at the same time.
* It prevents NPCs from joining the party for roleplaying reasons. A cohort couldn't join unless someone has the Leadeship feat--because if you let them join, that invalidates the Leadership feat and ignores the mechanic and if you do that, why have the feat and the rules in the first place? If an NPC joins the party because of the ongoing story, what happens later when a different PC takes the Leadership feat? Why should the second PC have to sacrifice an important feat slot to have something that already exists for free?