Have you considered cribbing ideas from SF X Tekken? As in gameplay wise. An example:http://www.youtube.com/watch?v=KJvA61RIfNc
A much better example.
I actually had a similiar idea where you can pair two specific characters with each other and they throw a unique Super Attack together instead of mixing their usual Supers, but I eventually did away with it, because then everybody would be picking only one or two specific pairings on that feature alone. As far as game mechanics are concerned, I'm mainly going by that of the earliest VS games (X-Men VS Street Fighter
and the like).
For characters where there others that you have considered or still consider?
There's a lot of Street Fighters that I would have loved to consider, but I had to set a cut-off at some point. I tried to keep a balance between the shoe-ins (Ryu, Chun-Li, Akuma), the fan-favorites (Zangief, Ibuki), and the obscure (Lucia, Ingrid). And of course, there's my rule of pairing them with SM characters based on themes. With Sailor Moon, it was harder. The Sailors, Beryl, and Tux aside, combat-capable choices were tough to make. Heck, Katarina probably wouldn't have even been a thought if it weren't for KungPow making her playable in his Sailor V game (I'm glad he did: she would've rocked as a recurring character).
I suppose (theoretically, of course) I could add a few DLC characters down the line (though knowing Capcom, they'd make me build a whole new game for retail instead).