Agreed. And it's a shame, because there's enormous potential not only from the story of Soul Calibur but the entire general premise of having a Story Mode in a fighting game. Mortal Kombat gave us a peek at what it could be.
Consider what makes stories interesting - conflict. And the whole experience of a fighting game, everything that could be understood as the "game" part of it, happens in conflict between two combatants.
All that's required is the creation of compelling reasons for bringing the characters into conflict with each other. The existing archetypes used to design fighting game characters already fit right in to this idea. They're warriors, mystics, fortune tellers, megalomaniacs, evil sorcerors, secret agents, angels and demons and everything else. It's a kitchen sink of pulp action tropes.
Bioware games are highly replayable, even though they're very time consuming. The replayability comes from an element of choice. We're already used to fighting game story modes with multiple endings, one for each character. Why not take a cue from ME/DA/KOTOR and create a tree-like story with diverging narrative paths?
Imagine a story mode where a friend can challenge you online while you play, thereby cue-ing up a cinematic where the challenger appears. Or a boss fight where you can enlist a second player or online friend as a tag team partner, and the encounter dialogue differs based on character choice. Imagine if a writer sat down and came up with a brief scene for each pairing of characters in story or versus mode. Something that, when assembled into a sequence, creates an overall narrative arc. Think of "The Truth" in Assassin's Creed 2. That's only one of many ways it could be done.
From a certain perspective, story isn't required at all in a fighting game. In most cases it's window dressing that exists to facilitate the action of the characters, and ultimately that's what matters most - the fun and challenge and depth of the fighting. But I feel like I'm not the only one who always sort of craves a story in these types of games.
Maybe it's the latent sense of conflict in the image of two visually striking, extremely competent and dangerous characters engaged in a duel to the death, which always takes place in a visually compelling diorama that hints at the edges of a story but never gets around to really telling it.