The fighting polygon team is MUCH harder to beat without losing stock on "Very Hard".
Metal Mario can cause problems, but if you stick to a strategy of attacking with your longest reaching moves and then running away before he hits back, it's not all that hard. Remember: the downside to Metal Mario's "metal-ness" is the fact that he's slower than Dick Cheney disclosing secret torture programs.