interesting points all! i like the 'interview needed' quality of the followers, and may just go that route...
i run two campaigns and have only used leadership in the one, but want to introduce it to the other in a different format.
basically, in the campaign i play with the wife and her friends, leadership gives the cohort, and the followers only come if you've a permanent stronghold (we rub out the +2 they normally give); this enables people to be covert without attracting attention, but, should they acquire a sizable lot of land, they can then have their 'normal people' allies move in to help out and generally support their efforts. imagine a benevolent, adventuring lord who is kindly to his serfs and retainers.
in another campaign with old school friends, i'm thinking of doing the 'you get them anyhow, but they're from the local community and mostly stay there' almost akin to a well-connected mafia don who knows he can rely on the locals under his wing for information, help and assistance (except instead of the mafia, he's a nice, well-intentioned guy!); they'd mostly live at their own places and have their own lives and whatnot, but they could lead to interesting plot-hooks!
as for the followers, i'd probably run them as non-elite statlines (13, 12, 11, 10, 9, 8) and only allow them NPC classes - with the addition of Magewright, since we play a Realms campaign and it seems to really add to the 'high magical fantasy' theme of the setting.