Being "deserving" is simply an aggregate of the other qualities people value in a character: being iconic, being important, being well-known, and being popular. Basically the qualities that make a character a big name.
And obviously those things are important, being "deserving" is just a divisive qualification because one, people are too cavalier in throwing it around, and two, as the bar for entry lowers with each Smash the "big names" run out, yet people cling to the "deserving" mantle because it did apply more justifiably in past rosters when the majority of (non-clone) newcomers added were legitimately big names. Now most of the additions fall under the category simply of "nice to have" instead of iconic, important or indeed "deserving", which I believe extended only to Villager, Mii, and debatably Little Mac this time around.
As it stands now, the only remaining omitted big-name iconic characters (in other words "deserving") would be Toad, Ridley, and K. Rool. Some might argue Dixie, but that in itself shows that while some general agreement can be found over who is "deserving" or not, it will always inherently be subjective. Though I believe at one point it did hold merit as far Smash goes, however that time has passed.
That's not to say being "deserving" is the be-all-and-end-all of inclusion, because not only are there other factors like potential among others which come into play, but with Smash 4 it seems that as the big-names had mostly already been included up to that point, the focus shifted from "big in general" simply to "big in the last few years".
So yes, I would say "deserving" was an apt way of describing characters back when the roster was made up mostly of the biggest names Nintendo had to offer, or at least names from the biggest series Nintendo had to offer (plus clones and the odd exception or two) but now that it's pretty much based on just what made a splash since Brawl, it's time to drop that qualification, it no longer applies. Just like how Smash is no longer prefaced by "Nintendo's All-Stars".
(I also excluded third-parties because that's a whole other set of standards as far as I'm concerned)