Personally, I do not like to admit that a character is "too good." Rather, I try to find any weakness he may have, and exploit them. MK's weaknesses are:
Limited kill moves - he must approach a few very specific ways if he wishes to take a stock.
Diagnol attacks - an attack by a small frame character (haven't tested it on the big ones yet) from an angle will not easily be punished. Watch out for Up-B however.
Projectile spam - MK has no projectile. He must get close to hit you. He makes up for this with good ground speed, but somewhat lacking air speed. Projectile users who can force MK back have a chance.
Limited air movement - his air speed is slow, and can be abused occationally by characters with a faster air speed. This is VERY hard to do.
Range - good spacing can occationally give MK problems (like everyone else).
Battle plan for MK - spam until MK's approach. Ground - short hop an air through his shield, continue a short-hopping barage, land behind him always and attempt grabs when possible. Get him away, and make sure your attacks hit at the tip when on the ground. When he is far away - spam as much as humanly possible, and abuse projectiles until he is forced to return. When MK is in the air, spacing is essential, and if possible, an attack from beneath him and to the side would be ideal (A tether attack would be the ideal example). If MK uses a short hop aerial, this is the most important time to remember spacing. It is essential to out-range his air with a ground attack. Or you could try shielding, and seeing what he does next, depending on the relative height of the shorthop to you character. You might be able to shield-grab MK, or take advantage of a small mistake in short-hop timing which allows you to attack from a shielded aerial.