It might be interesting to play through the Baron portion of the game with a party of Cecil, Rydia, Edward, and Yang to see how far you can get. The team is certainly limited because of the equipment restrictions for Cecil and Edward.

I would imagine that Cecil would wind up in Mysidia somehow regardless of the events unfolding in Baron.