I thought I would browse the reviews of MK9 last night and overall they were positive, but many reviewers took a point or so off because they said the bosses were cheap and too hard (oh noes!). While they might be over-powered, they are not cheap like some other fighter's boss (cough cough Seth cough cough) and the pattern to beat them is quite simple.
I am by no means one of those "fighter guys" who obsesses over games and know them inside-out, but even I figured out how to beat them, so it can't be THAT hard.
General:
Throws are disabled... period. Just accept it. Strangely enough, X-Rays aren't. This doesn't make sense to me seeing as how an x-ray is just a suped-up throw, but whatever.
Uppercuts and sweeps are NOT randomly negated. They are negated only when chained in a combo or if the boss is "on guard". They key is to hit them with it when they are off guard. Bosses are off guard for a fraction of a second when they just get up or when you've just jumped over them. Except for Khan, bosses are also off guard when you've just landed from a jump. Note that the "off guard" window for Shao Khan is very slim compared to the other two.
Do NOT rely on your specials and combos! You rely on your dodging ability and patience to win. Certain bosses are weak to certain types of special moves though and by all means exploit that, but unlike regualr characters you can't spam the specials, you must wait for an opening.
Uppercuts are your friend! They take a lot of damage and get the boss away from you, allowing you to get ready for the next attack. Again though, they don't work when the boss is on guard.
Goro:
This guy is all business compared to the other two... fortuantely he is slow as dirt. Jumping around a lot and then attacking on the landing works well. Fireballs work as well, but only until he counters with his own. Charging attacks (shadow kick, raiden's superman move, ect) work well on him be do them as he is about to launch and attack. You really shouldn't have any problem with this guy.
Kintaro:
Kintaro's a show-off and it helps us to no end. They key to this guy is just to dodge his attacks. Every few seconds he poses, giving you a free hit. Also if he misses his teleport stomp he poses again, giving you another free hit. So the way to beat him is to keep your distance to avoid his close range attacks, being ready to dodge his stomp at any second. When he's open, go in for an uppercut or use an enhanced special move if he is too far away. Jumping over him and uppercutting him works as well.
Shao Khan:
This is really the only challenging boss, and he makes up for it by being really hard... think UMK3 hard! In the old days the way to beat shao khan was to jump over him a lot and this is still true, but now he has special moves to take care of people who try to jump over him, so the window in which you can do damage is greatly dimished. First off, you have to dodge all of his attacks if possible because they do a LOT of damage... his hammer throw in particular must be avoided.
There are two methods to beat Khan and which one you use will depend upon your skillset. The first method is to dodge every one of his attacks (note I said dodge, NOT block) you have to dodge every attack perfectly, without fail. If you do he'll eventually taunt you and you can go in for your free hit. This method required a great deal of patience though as the amount of damage you can do in that free hit window is very small so you'll have to repeat this process several times.
Method two is far more critical timing-wise, but it's easier if you can move fast enough. Walk towards Kahn, being ready to dodge and attack at a moments notice. when you are in range jump towards him and hit him with a regular punch as you land. Then while he is stunned jump over him and uppercut him from the other side. You must be almost on top of Kahn when you jump over, or he'll hit you with his hammer. Sometimes he will anyway, in which case you need to back off! Just repeat that process keeping the following things in mind:
1. If he cancels your uppercut you need to do a foot sweep immediately! If he cancels that back off! If not jump over his head.
2. Sometimes during the fight you will find yourself some distance from Khan... when this happens wait for an opening and use a charge attack on him to close the distance. (An "opening" would be just before he throws a hammer or during a taunt.
3. Sometimes the jumping punch doesn't work! If you are having trouble, you can walk towards him, punch him a few times on the ground (he will block them) and immediately jump over him.
I hope this helps a little, because the story mode requires you to fight every boss a few times and it is very much worth completing.