I've been testing a few things and found that Dash attack, Usmash, and Utilt have insane priority. I wasn't sure where to put this, but since the topic of discussion is MK, someone who outclasses us because of the whole priority issue, I figured it'd be acceptable.
I've found that, unless the attack vastly outranges it (TL's Dair, or Link's Dair), then Mario's Usmash will hit right through it. I also haven't found a single smash or anything that beats Mario's Usmash. I've tried Marth and G&W's Fsmashes, DK's Dsmash, a bunch of Pit's moves, and other random smashes. Utilt and Dash attack also clashed with some of these high priority attacks.
My point, the general idea for fighting MK is to camp him and keep smashes fresh for the low % kill to take advantage of his light weight. If you play too aggressively, he'll always win since he runs right through everything you do. However, if you use Mario's 9-frame Usmash a little more aggressively than normal, you can rack up damage a little easier than your normally would. Of course, your most reliable KO move in this matchup would be stale, but now MK's pressure isn't a *****.