Deserve is a really strong word and I really don't like to use it all that much anymore because of how its really driven by opinions rather than fact. You can argue that any character deserves to get in and, within your own logic, you'd still be right. As my posting history would tell you, the word is pretty much debate bait.
Now, for what I think:
1. Megaman has a long history that goes back to 1986, he has close to 100 games, and he has appeared on every Nintendo console except the Virtual Boy. If I had to tag the word deserve to any third party character, it'd be him.
2. Final Fantasy's weird. It really doesn't have a main character to represent the entire franchise. There's Mog and the Chocobo but I still say its iffy if either could effectively carry the weight of representing such a major franchise in gaming. Definitely an important franchise but freakishly hard to effectively represent.
3. Castlevania also has a nice history with Nintendo and has also had a game on every Nintendo console except the Virtual Boy. The only problem will be if Snake stays around because both Castlevania and Metal Gear are Konami franchises. Third party spaces are limited and it's assumed that third party representation will be spread evenly to avoid any one third party getting more share of the game's profits then another.
4. Enix and Nintendo have had a strong relationship even before Enix became a part of Square to form (Oh my God, what is he going to say?!) Square-Enix. Dragon Quest is a titanic franchise... in Japan. It is one of the top selling video game franchises... in Japan. Sakurai said that he didn't want to show bias to any one particular region when it came to character selections and with third party spaces being so limited, he may want to step over this option altogether.
5. Soul Caliber is Namco-Bandai. It has only had two games released on Nintendo systems since 2003 despite 4 being made since that time. I'm also not sure how well the characters of Soul Caliber would work in a Smash Bros setting. Granted, Snake worked but they pretty much made him a clean slate to make him work. Like with Final Fantasy, who would be the main character to represent the franchise? Nightmare? Mitsirugi? Ivy? Once again, a very tough call.
6. Bomberman has had games on Nintendo systems since 1986 and has appeared on every Nintendo consle except the Virtual Boy. He is owned by Hudson Soft which is an extension of Komani. There's one problem. Another is that Bomberman's influence has definitely fallen in recent years. It was never really a huge franchise to begin with but now it's reached a level of meh-ness that's seen in other franchises like Crash Bandicoot and Spyro. Is he iconic? Even if you asked me this question 10 years ago, I would have told you that it was debatable.
7. Two games with shattered cameos through-out probably close to a dozen games. The first roadblock is that its own by SEGA which already has Sonic has their main man and unless things drastically change in the next five years, Sonic isn't leaving Smash Bros. Is NIGHTS iconic? Not really. If anything the first NIGHTS was a cult classic while the second game got average scores. If you ask me, SEGA should just stay with Sonic because when it comes to their other characters, no one else really comes close to the star power that he has. (I'd personally say that Ai-Ai's in a distant second place.)
8. Great franchise but it hasn't had an installment since I believe 2006. Also, it's owned by Konami. It also doesn't really help that the franchise is virtually unknown outside Japan and hasn't had a game in North America since, I believe, the year 2000. I'd love to see Goemon come back eventually though but I don't think Smash Bros is the place for that.
9. I have virtually no opinion on Bubble Bobble. I can't really think of any good reasons for them though aside from the franchise having as long a history with Nintendo as Megaman, Castlevania, and Bomberman. How iconic they are is also debatable.
10. Tales of Symphonia was just two installments out of twelve in the Tales of... franchise. Lloyd has been playable in three games making him, I believe, the Tales of... character with the most playable appearances. As he's Namco-Bandai, he has competition with several other characters including Pac-Man.
11. Muramasa will probably end up being a one hit wonder. There's not really anything else to discuss unless more installments come in the future or the fanbase for it really upsurges.
12. I don't really have an opinion on Street Fighter aside from how I'd prefer to see Megaman represent Capcom. Darkstalkers hasn't had a game since 1997 so that's not really up for debate. It's had loads of cameos since then but that's about it.