We use Leadership often in our games, but then again - my group has a serious love affair with owning strongholds....
Case in point: one of my games, the PCs decided to found their own community, and got permission from the local noble to do so. In addition, they decided that - since their community would be on a heavily-traveled road - they would like to establish a toll. Now, they just had to figure out how to gather enough people to not only establish a community, but enforce the toll.
No - save one - player wanted to bother taking Leadership though. They had plans for their character builds, and Leadership did not fit in well. However, the one that took Leadership decided that once his Cohort reached 6th level, he would take Leadership as well, as would the Cohort's cohort, and so on down the chain.
I okayed it. Why? Mainly because it made sense, and it would be multiple levels before the Cohort could even take Leadership, let alone the Cohort's cohort, and so on.
By the end of the game, they had a community of 40 people. 15 of them were hirelings, and 10 of them were people that settled down. Only 15 were followers.....nothing overwhelming there, I would say. (BTW, the game ended when a fairly powerful (15th level) necromancer attacked the town and killed everyone but three PCs. Low-level followers - especially using 3.0 rules - are not powerful opponents of the undead. Those three PCs went on to become the King's Spys, and also became the various relatives of PCs in the new game.....such stories were told of the Thorp of Tollhaven.)
Just sharing my experience.