Mysterious characters are a very useful tool, but only if you are planning on doing a sequel. If you end up including a character that is really badass and mysterious, your audience instantly wants more. If they know you aren't going to give them more, they instantly think the campaign is unedeveloped in some aspects. Fans have a thirst for knowledge when it comes to the stories they like; If you plan to include stones unturned but you won't turn them over, you might as well not include them at all.
IMO, the most important aspects in a story are the broad topics characters plot development. I'd say that characters are 60% of it and the plot is 40%. The reason being that, if you look at what blizzard does, the reason why people like their games is more because of the characters and their backgrounds than because of the story. A characters behavior is much more intriguing to the viewer than the actions. Take the first terran campaign for example: Arcturus' efforts to destroy the Confederacy are completely overshadowed by his personality. IMO, the event of him betraying Kerrigan on New Gettysberg is the key moment in telling the player who he is. As soon as that happened, everything else along the way seemed so little and miniscule. Even his decision to save Duke and bring him to the SoK was a powerful event that defined him as who he is. Each of the campaigns has moments like that; moments where a character's actions completely takes the spotlight and everything else gets almost completely belittled because of how powerful the moment is. In fact, you could argue that most characters have a similar moment, but there is one single event in each campaign that stands out above the rest.
Episode I: Mengsk's betrayal of Kerrigan
Episode II: Kerrigan's releasing of her full powers on the Amerigo
Episode III: Tassadar surrendering to the Conclave after being appalled by the bloodshed of his own people
Episode IV: Aldaris' rebellion and attempts to expose Kerrigan himself
Episode V: DuGalle realizing, after he had Stukov killed, that his trust was misplaced and he betrayed his friend
Episode VI: Zeratul's killing of Raszagal to release her from Kerrigan's control
Notice that all of these (except Kerrigan releasing her powers on the Amerigo) happen right before the final mission and finale of the story of each campaign. These moments define the aspects at the core of each character. Think of the rest of what they show you almost as a mask. It's only when these events happen that the mask comes off and you see what makes these characters who they are. After these moments, you never really look at the characters the same way again.
But characters and their motives are nothing without a good story. The story is part of what defines the characters as well. It shows their goals, their fears, and their downfalls. I personally believe that stories, in reality, are actually tools used to give characters more emphasis and meaning. Sure, stories are the basis of your writing, but how you integrate the characters into it makes all the difference. Think about Command and Conquer 3: Tiberium Wars for a moment. They're story is a decent start, but their characters suck so much and are so tow dimensional that you lose interest. You can't relate yourself to the story if the characters are replaceable.
Sorry if I'm stating the obvious some here, but that's how I see it.
"Imagination is the beginning of creation. You imagine what you desire, you will what you imagine and at last you create what you will."
-George Bernard Shaw
