I'm a big fan of multiple endings, especially if you can still have some influence over them late in the game (so that you don't need to replay the entire game every single time to experience every ending). Since it seems character based, you might look at what FF6 or Ogre Battle did for endings.
In FF6, every trigger (in this case, recruitment) was simply added on to the overall ending. So the endings didn't differ so much as became fuller.
Ogre Battle, meanwhile, gave a recap of all the major characters in your group at game's end. This recap would vary by character based upon actions, but again more or less built up through the game rather than have strictly separate story lines.
Of course, you could do strictly separate story lines. I just figured I'd throw out a couple of other thoughts.