Midna and Vaati both have moveset potential, not only Midna has those forcefield things she does to defeat the Twilight enemies when she is on Wolf Link, her hair could serve as a grab, the attack she used to kill Zant, she also has an already there Final Smash, which is the Fused Shadow transformation, Vaati can turn people into stone, has enough magic to make a moveset from and he has also the transformation from the final battle of the Minish Cap, they all have moveset potential, not to mention the other fact, that they are currently relevant to the Zelda franchise, Skull Kid despite having that said cameo in TP, it still doesn't make him important nor is it a role that has any merit to grant him an appearance, let alone representing Majora's Mask.
So as much of a struggle it is to formulate a moveset for Midna and Vaati, I can see that it's possible. I already know that they each have a few moves here and there, but it's really not as all-out complete as Skull Kid's moveset. To me, Skull Kid is just a character waiting to be added, and the only thing stopping him is that he isn't "deserving enough." I feel that is a shame and a massive waste of potential.
All three of them have movesets, but in my mind I had the idea that Skull Kid would separate from the crowd of "generic moveset" characters, because his playstyle is more in the realm of Ice Climbers and Pokemon Trainer.
In Skull Kid form, he would be a weak, light, and evasive character. But his Majora form would temporarily be able to manifest itself and battle until it got too exhausted. This is sort of a mechanic which combines the Pokemon swapping of PT and the transforming of Zelda. Majora himself would be a strong, heavy, and powerful character -- essentially the perfect balance between "underpowered" and "overpowered". On one hand. Skull Kid would be a low tier character, but then he would have the ability to magically transform himself into the highest tier character in the game. Again, this is all speculation, but it's cool nonethless.
The reason I mention this is because when it comes to a list of bland, generic, and uninspired characters, Sakurai clearly favors ones who stand out from the crowd. A prime example of this would be a list of potential Pokemon candidates, and then the Pokemon Trainer. Sakurai's choice is an obvious one.
His Final Smash is also such a stunning ability that it's worth representation in Brawl alone, either by AT or otherwise. I would settle for Skull Kid as an attack trophy, but to be honest, he is capable of much MUCH more than just that, and I would rather not see it all go to waste.
But in the end, you claim all of the possible Zelda characters can form some fragment of a moveset. True, but I personally don't feel it would be as in-depth as Skull Kid's as I explained above, and this is why I think Skull Kid wins this one over them.
However, for my next point, you basically replaced "classic, reoccurring character" and said instead that Midna and Vaati have more relevance to the Zelda series at the present time.
It's true, they are more relevant and you've proved that Brawl clearly showns signs of that. The stage, the weapons, all of that Twilight Princess material that you pointed out to me. But as I said before, Brawl will be a game that is played for many years from now, and there very well might be another, newer Zelda title by then.
You might say, didn't this same thing happen in Melee? Yes, with Majora's Mask.
Majora's Mask also had a stage, and the entire Zelda cast was all based off of the current games, including weapons and spells among other things. Everything we saw then is happening in the next generation of Smash Bros.
But there was one thing they opted not include -- a character from that "generation" of Zelda games. So I'm asking, why should they include one now? How is this fair? Why is it necessary to completely "skip" over past characters who previously held priority, and then leave them behind to rot?
Because of Majora's Mask, Skull Kid has become a fleshed out character with his own unique image (The mask itself is one of the most amazing pieces of character artwork ever designed) and simply does not deserve to be forgotten so quickly. If it weren't for his starring role as the main villain in that game, he wouldn't be such a valid candidate in the first place because he would still only be a "lame cameo character" as you put it. However, this is no longer the case as he has become much more than that, and you realize this.
But then again, as generations pass characters become outdated, including Midna and all of the other one-time-only characters. Until the next Zelda game proves otherwise, Skull Kid has become a staple character in the franchise and will survive longer than most of the characters you suggest. I say why not include him now so when you pick up the next Zelda title and you see him again, you can say, "Oh, Skull Kid - he's a relevant character," instead of looking at the Brawl roster and saying, "Why is this no-longer-relevant character in this game?" It is in this sense that again, by looking at the bigger picture, I can see that Skull Kid wins this point as well.
To me, all of the Zelda candidates are on the same level and each have their own advantages and disadvantages. But whoever does make it, if any of them do, I just wish more people would realize that Skull Kid was just as deserving as all the others.