During Konquest you of course run into any of the 24 characters on the select screen, but of course there are others. Here is a list of everyone I've run into, and where, and sometimes when. These are only the MK fighters you cannot select on the select screen. This is long.
Johnny Cage=Outworld E8 near Li Mei's village. You can fight him
Kano=The first time you enter Outworld
Classic Sub-Zero(?)=Earthrealm in Shujinko's village
Sonya Blade 1st=Outworld A5 she'll give you some koins
Sonya Blade 2nd=Chaos Realm D7. You can fight her
Reptile=Outworld Living Forest D4
Shang Tsung=Netherealm B8 you can fight him
Goro=Netherealm. Seen laying dead inside one of the huts
JAX 1st=Earthrealm E4 you can fight him he guards the bridge
JAX 2nd=Orderealm C5 you can fight him again
Kitana=Edenia near the fountain B5
Kintaro=Edenia sometime during the night near the camp E8
Shao Kahn=Outworld A5 stone village
Stryker=Orderealm anywhere near the blue walkway
Cyrax=Netherealm near the bridge where you fight the 3 Black Dragons
Sektor=Edenia D3
Mavado 1st=Edenia near the Palace
Mavado 2nd=Orderealm near the portal
Hsu Hao=Edenia E5 behind one of the huts
Motaro=Earthrealm first time you enter near a hut
Nitara 1st=See Cyrax above
Nitara 2nd=Outworld in a cave E5 inside the Tarkatan village in back
Meat=Netherealm cave at 11PM he'll give you 1000 Onyx koins C8
Rain 1st=Outworld A7
Rain 2nd=Edenia C6
Mokap 1st=Chaosrealm C1 near the transporter
Mokap 2nd=Orderealm near blue town dancing. Hit him please.
Sareena=Netherealm=A8 behind the hut behind Tsung
Drahmin=Netherealm A4
Moloch=Netherealm E4 across from where you see Cyrax and Nitara
Frost=Outworld E5
Shinnok=Netherealm around the corner from Shang Tsung
Jarek=Netherealm across from the guard station
Reiko 1st=Outworld near Li Mei's village
Reiko 2nd=Edenia near a cliff
Fujin=Orderealm near the portal
Quan Chi=Netherealm near the temple
Blaze=Outworld near one of the Pit II bridges
That's everyone I've seen so far. Of course everyone you can select on the select screen are scattered throughout Konquest as well. The only ones from the past I haven't seen are Kung Lao, Kai, and Sheeva. Has anyone seen them anywhere yet.