I just beat MKII on PSN MKAK, and here's how I did it:
Around the middle tier of the ladder, I used the Baraka blade chop spam approach as stated above. This worked well until I got to Kintaro.
Kintaro is an absolute beast. I fought him for at least an hour without winning a single round. I started using Kitana as I discovered that Kintaro liked to walk into her fan lift, setting him up for a routine jump-punch/air-fan-throw combo, but it still wasn't effective enough. I'd occasionally win a round, but he'd always find a way to sneak in a teleport ground pound and take me out.
In my frustration, I searched YouTube and found a video that demonstrated an easy way to beat him with any character using well-placed jump kicks. Sure enough, it worked, and I beat him in my first try after that. Here's the link:
http://www.youtube.com/watch?v=1TeCQZqUgZ4
Next up was Shao Kahn, and for him I reverted back to the Baraka spam tactic which worked on the first try.
As much as I hate using spam tactics, it becomes obvious deeper into the game that the AI is finely tuned to counter just about every conceivable attack. Forget trying to throw, you will ALWAYS be the one getting thrown.