I could definately see a Mortal Kombat character working. Here is why.
Smash brothers should represent characters from different genres. Side scrollers (Mario), first person shooters (Samus, Fox), mini games(G&W), strategy games (Fire Emblem), RPGS (Zelda characters, Pokemon), racing games (Captain Falcon) ect. A fighting game is missing.
And personally when I think of a fighting game Mortal Kombat is the first to come to mind. It generated a movie, it revolutionized fighting gore, and it is still kicking (which is pretty decent, because many fighting games don't have great staying power). It may not be the best fighting game by a long shot, but almost everyone knows about it. The older generation, who don't play video games, remember the controversy it caused.
Now with the addition of Snake, it is possible to have characters from a bloody game. He slit throats and shoved people in lockers, but he made a great transition into the Melee World. Smash emphasizes the goofy part of games. Having Scorpion (rendered with Smash graphics and under the eye of Sakurai's knack for detail) scream out get over here while throwing out his harpoon would be great, especially after Captain Falcon taunting the ninja with "Show me your moves!"
Of course Scorpion's moves can be worked to fit the game. He wouldn't telport to the other side of the stage with a punch. (Although it could work for a backthrow. Scorpion could disappear after grabbing an oppenent and come sailing it from the other side, super fast, and punch the character in the other direction before it could move. This way Scorpion could hit others in the way while the move would be fair (could only be used if he grabs someone) and Scorpion would be susceptable to attacks while flying across the screen). See how Smash emphasises the goofy parts of games, even games with blood galore.
I say Scorpion or Sub Zero would be the best candidates. I would vote for Scorpion.
Scorpion's Moveset:
A: A quick punch accompanied by a ninja grunt
AA: A quick punch, followed by a strong outward palm strike as he grunts again
AAA: Jab, open palm (with opposite arm), and then he swings arm (opposite other arm) in a clockwise circle striking the oppenent on top of the head with an open palm. Hits oppenent toward the ground, could bounce up the enemy for a combo
Toward A: Steps forward with a bent knee and launched both arms forward with palms open (looks like Lui Kang's animation when he shoots a fireball)
Down A: Old fashion MK sweep kick
Up A: Old fashion MK uppercut
Forward Smash: Scorpion slides one foot back, and then crossses his arms over his head while reaching to his back. He grabs the hilts of both ninja swords strapped on his back and then unsheaths them and swings them over his head and toward the ground in one smooth motion. The swords are crossed (because he crossed his arms to pull them out) and appear as a flaming X. The blades are made out of pure fire and leave a trail of ash. They fizzle out when they hit the ground. There is a burst of ember around the sheaths and the handles materialize back where they were. Lag in the begginning but fair range and strong knockback and attack.
Down Smash: Scorpion stands up straight while either facing the screen (or having his back toward the screen). He raises his arms straight above his head and tilts his chin up. Fire spouts in a circle around his body and rises shoulder high before extinguishing into billows of smoke. Quick to start up, bad knockbad, but pretty good damage depending how close the person is. Some after lag.
Up Smash: Scorpion crouches down and looks up with one arm bent at his side. In his hand a ball of fire starts to form. The longer the charge, the bigger the sphere of flames. While he is charging one can vaguely seen translucent images of ghosts spiraling from areas near scorpion and towards the center of the ball. The ghosts can even be images of other MK characters. Then Scorpion hurls it upwards. The fireball shrinks as it goes up (and loses knockback power the higher it is). Screams of ghosts are heard when he tosses it up. Could travel near the top of the screen on some levels if fully charged. Leaves trail of embers and ash.
Throw: Scorpion reaches forward with both arms to snag himself a victim. (The harpoon I am saving for Toward B).
A: Scorion's eyes blaze orange and smoke billows from his hands. He steadily burns the enemy.
Forward throw: Scorpion holds the others arms, then leaps off the ground, curls his knees to his chest and places his feet on the other character's chest (center of body) and then kicks off sending the oppenent straight back.
Backthrow: Scorpion teleports into a blaze of orange swirls. A teleport quickly opens in front of the oppenent, but a few paces away. Scorpion shoots out (in the position he does the teleport punch) and sends a fist into the oppenent's chest. Hits anyway in the way. Any other character caught in his path goes up, but the oppenent is sent backwards in a straight trajectory.