If people tried using link, they would lose 100% of the time against a good player. He wasn't that special.
The game was 480p (not HD) but the Xbox version would scale to 720p.
I'm going to have to disagree with the notion that there was never a scenario where Link could win against a good player. For a long time I think the community had written off Yun sung (Yunsuck as he was called) as utter trash. Yet, in world tournaments of the game there were still minds out there that were able to make viable use of him in high levels of play. I believe there are minds out there that could have done well with link in the same capacity.
The question is, what would be the point of such an investment? Being a "fun" character in a gamecube exclusive of the game with a terrible controller for fighting games, he would never be allowed in any serious kind of session and would hardly be worth the investment of time to learn intimately. Despite that, just because no one playing as Link was able to defeat you, that doesn't necessarily mean no one under the sun ever could.
As for resolution, the Xbox didn't "scale" it to 720p. It rendered it at that resolution, though it could only manage it in a 4x3 window for performance reasons. If all the Xbox was doing was scaling it, there would be no reason not to output the matches in anamorphic widescreen as well like it did in 480p mode.
For that matter, if all the Xbox could do beyond 480p was upscale then EVERY Xbox game could have passed itself off as a "720p" game. But that was not the case as only a small handful of games supported it. But don't get me wrong, I know where you're coming from. You probably heard Halo 3 isn't running in native 720p (and it isn't) along with several other games on the system and probably just figured no game in existence on xbox or 360 ever has.