Mortal Kombat - Did You Know Gaming? Feat. Two Best Friends Play
According to Ed Boon, Warner Bros. suggested Neo from The Matrix as a guest character for the game but the idea was turned down because the character didn't fit in a game like Mortal Kombat.

"It was more like 'We’d love to do a guest character, who’s available?' And then we would see a list of 10, 15 characters. I remember they brought up Neo. So there were a whole bunch of ones that for business reasons or that creatively we didn’t think they’d fit."
Contributed by ZpaceJ0ck0
An unused audio file suggests that Brutalities from Ultimate Mortal Kombat 3/Mortal Kombat Trilogy were going to return. However, they were cut from the final game, though they would return in Mortal Kombat X.
Data for an unfinished version of Skarlet can be found within the game's data. This version uses Jade's stance and Mileena's profile picture as placeholders, along with an additional costume not seen in both the home console or PC versions' DLC. This costume would later be made available in the PS Vita releases of the game.
Contributed by RyuHane
When performing Fatalities on Kratos, he will have different reactions to some of them. For example, Johnny Cage will not plant a trophy in Kratos' head when Cage performs his "And The Winner Is..." Fatality.
Ed Boon has said that Sweet Tooth, from Twisted Metal, was considered as a guest fighter at one time during development.
Contributed by gamemaster1991
During development, Sub-Zero's human form was going to have a counter move called, "Icy Counter." But it was given to his Cyborg form instead.
When the player selects Noob Saibot and presses Start after selecting his classic MKII skin, Smoke in his MKII skin will assist him instead of his shadow on throws, X-Ray Move and Fatalities. This could be a reference to the Tag-team alliance in Mortal Kombat Deception.
Ed Boon has stated that he was planning to include one character exclusive to the Xbox 360 version of the game. He also said that most of the development team had Twitter accounts so they could directly interact with fans of the series, and often paid close attention to what fans were saying.

Fans made suggestions about including Master Chief (Halo) and Marcus Fenix (Gears of War) as playable characters. In an interview with Eurogamer, Boon didn't put much detail into why they weren't approved for the game. He stated, "I'm not allowed to talk too much about it, but that is all I can say. It was not a decision we made where we said 'Oh, let's not do one for the 360.' Anybody who's really knowledgeable about the Xbox video games, the big titles, names like Master Chief from Halo, Marcus Fenix from Gears of War, and any other Xbox exclusive title, is going to come up in a conversation in talking about it. So clearly, we've discussed it."

Why NetherRealm Studios weren't allowed to use them as playable characters for Mortal Kombat remains unclear.
Contributed by Tuli0hWut
Tremor, a character who appeared in Mortal Kombat: Special Forces, makes a cameo appearance in the Vita release's Challenge Tower. He shares his icon with Noob Saibot, fighting stance with Smoke, grunts with Scorpion and the Back Breaker move with Jax.
Contributed by Mass Distraction
During the game's story, when in Cyber Sub-Zero's first-person perspective, he rapidly looks through images of other Kombatants: Bo Rai Cho, Daegon, Frost, Motaro and Kenshi.
Contributed by DrakeVagabond
Meat, a fighter from Mortal Kombat 4, can be seen in the Cathedral stage on an alter being sacrificed by a Shadow Priest or Rain. It cannot be confirmed that this is Meat however, as his appearance here does not relate to any known background story of his.
Contributed by DrakeVagabond
Sonya's alternate costume is based on her appearance in the 2nd Mortal Kombat movie.
Contributed by DeerBoarDude
If Skarlet performs her "Make It Rain" fatality on Sheeva, 6 pillars will rise instead of 4. This is the only fatality to be altered specifically for Sheeva's 2 extra arms, although it cannot be performed on Goro and Kintaro. If it is performed on Kratos, he will attempt to break the pillars instead of panicking in fear.
Contributed by ShyanVixen
There are audio files which indicate that Fujin (the wind God from Mortal Kombat 4) was set to appear in the game, but was cut.
Contributed by DeerBoarDude
Shang Tsung's "Bang Bang!" Fatality is a slightly modified version of The Joker's "The Killing Joke" Fatality from Mortal Kombat vs DC Universe.
Contributed by gamemaster1991
The monster that occasionally pops up in The Krypt to scare the player is a failed attempt at cloning Kitana. It can also be seen on the far left side of the Flesh Pits stage, where you first meet Mileena in story mode.
Contributed by ST3