This is done fairly successfully in LotR Online. There is simply a ton of different story arcs. You have specific class storylines. For example, as a captain I helped Boromir prepare for his departure from Rivendell, and then I got to see them off. The developers use single player instances in order to accomplish this. There are also rooms and areas that I can only enter at certain points,s o I won't run into Boromir again after I already helped him leave Rivendell.
Then you have the epic questlines, which are as well written and engaging as many single player RPG's I've played.
I think the whole story complaints about MMO's are overstated. It's very possible to create an engaging storyline in an MMO, I heard Wrath of the Lich King was a fantastic experience in that regard.
But whatever the story is, if you don't like the gameplay mechanics of MMO's, you aren't going to be happy with KotOR Online.