If his LEadership score is at 25+, then I assume he's fairly high level?
There are a couple of options you could look at. First, there's an "Epic LEadership" feat in the ELH that allows for more followers and higher level cohorts. I believe it has an extrapolated table for Leadership socres over 25. You could use that, or if you don't have that book just extend the existing table yourself.
I don't think that by the RAW taking Leadership again would benefit the player, as the feat isn't designated as one that stacks. Even if it did, all it would serve to do would be to improve your Leadership score, which is useless if he's already at a 25. Perhaps you could invent a new feat for him along the lines of:
Great Leader
General Feat
Prerequisite: Leadership, leadership score of 15+
Benefit: The character gains a number of additional followers equal to what they would normally receive with their current Leadership score minus 6. For example, a character with a Leadership score of 20 could attract an additional 15 1st level followers and 1 2nd level follower (as appropriate for a Leadership score of 14). The character may also gain a second cohort of a level appropriate to the modified Leadership score (in the example above, a second cohort of up to 10th level). This feat allows a character to exceed the normal maximum number of followers on the Leadership chart.
Special: You may take this feat more than once. The number of followers and cohorts gained stack.