... so the gameplay coming from making those choices would only be available to the first player who encounters it....
Sacred 2 solves it similar to this. Their single player version is just one of the MP modes the game supports. At any given time you can invite others who can play with you, but the story is still controlled by you and not the others. I'm not sure how rewarding that is for other team players though, but it does allow you to kill big bad monsters easily by inviting others
(Although the monsters are leveled differently depending on the size of the team.)
Still this type of MP support wouldn't suffice. At the very least an additional MP mode is needed where you can roam the world with a team and play side quests only as the story is irrelevant then. Access to quests would have to be restricted to only those quests that don't give too much consequences, or create MP only quests. Some item hunting wouldn't harm either
That said I think the SP version is the one that should be perfect, even if it means loosing MP support.
