I agree...
Mileena and Tanya! The two underestimated evils of MK, they are gonna rule oneday.
Also Kitana and Jade! They are the two good guys who are always over looked too, but they have the speed and skill to defeat most competition.

Sindel/Mileena (Amazing team of good and evil)
Sonya/Johnny Cage
Tanya/JAde (Same with the first)
Sonya/Kenshi
Kung Lao/Li Mei
Cyrax/Sub-Zero
Frost/Sub-Zero
Nitara/Ashrah

Mokap and The Fergality Dude...

Just adding my voice: MK7 should have tag-team modes. That would be awesome. I've always liked the feature in DOA and I think it would be awesome in MK. Tag-team fatalities and all. Maybe this Noob-Smoke idea will influence that decision. I love it!

Ermac and Kenshi (or Scorpion)

Sub-Zero and Scorpion (Fire and Ice, perfect opposites and they have no problem fighting everyone else since their weakness is each other)
Kabal and Havic (Good blend of Speed and Power)

Sub-Zero and Ermac or Kenshi.
Sub-zero freezes them and Ermac smackes around with his mind

Liu Kang and Kung Lao - Shaolin brothers together are a very cool duo.
Johnny Cage and Raiden - Thunder god and his revived follower, Johnny Cage is a skilled martial artist and Raiden would be his mentor.
Sub-Zero and Scorpion - Together, Quan Chi will crumble before them.
Kano and Sonya - Something would force these two to work together, and when they do they will be a very deadly team.
Kenshi and Ermac - Ermac would play the role as mentor to Kenshi.
Kitana and Mileena - Both sisters reunited would be a very deadly team.

Kenshi and Sub-Zero based on the bio.

Sektor and Cyrax by far...
Kabal and Baraka...
or any combination of the 4...

Sektor and Mavado
Shang and Quan (I'd love to play them as a team)
Dairou and Kai
Liu Kang and Shujinko

Scorpion and Ermac
Rain and Sub-Zero

Kitana and Scorpion