I can beat Mario 3 quite easily, but I didn't beat the original Super Mario until about a year ago. I have Punch-Out without the Mike Tyson endorsement, but Mr. Dream fights pretty much the same as Tyson. It took me years, but I finally beat him a year ago. I'm not sure what advice I have except just stay on your toes and never blink.
I've never beaten the second quest on The Legend of Zelda, and I've never beaten Zelda II.