I haven't fired this game up in a while, but I believe it is in the Extra Content section? If that's not the problem, and the game simply isn't "unlocked" despite your efforts, you could manually enter the cheat code at the menu to unlock MK2.
OKOKOK...Did you use the search function? I'm guessing no. Now...is your game the PAL version? If so...then you don't get MK II.
I know...very disappointing isn't it?
Q: I completed the Smoke Missions, but where's my Mortal Kombat II?
A: USA/NTSC PS2/Xbox version owners go to the Kontent menu in the game's main menu screen. EU/PAL PS2 owners prepare to be disappointed. It was disclosed during the Fight Night chat that Sony's EU Quality Assurance department said that the Start button bug in the Midway Arcade Treasures 2 version of Mortal Kombat II (the version included in Mortal Kombat: Shaolin Monks) was not an acceptable flaw; therefore, in order to pass Sony EU's QA process, Mortal Kombat II was removed from the EU/PAL PS2 version at the last minute. However, the EU/PAL Xbox version does contain Mortal Kombat II.