There are plenty of cross-over already, from a very famous one where people go "Oooooh" in nostalgia when playing it, to unpopular one that most people never heard of, or obscure one that though people know about it, they never heard from which series most of the characters come from.
========== YOU COULD SKIP THIS ONE IF ==============
======== YOU ALREADY FAMILIAR WITH VARIOUS =========
===== CROSS-OVER OR SIMPLY DON'T WANT TO READ IT ====
For those who can read Japanese, you can enjoy the Japan-only cross-over game like NamcoXCapcom game (SRWOG:Endless Frontier predecessor) with characters like from Rockman series, Dark Stalkers, and King of Fighters series. Or for those moe anime lovers, we have Dengeki Gakuen with characters from Shakugan no Shana and To Aru Majutsu no Index.
The new PS3 also have several, we have Cross Edge and Trinity Universe, featuring Gust and Nippon Ichi characters (and several other companies). Disgaea fans would be overjoyed with this game.
Don't forget Kingdom Hearts, featuring Square's characters and Disney ones.
From indie side, we have Battle Moon Wars from Werk. As the name implies, this game is heavily inspired (and similar) to SRW series and have Type Moon (or rather Kinoko Nasu's) characters like Fate/Stay series, Kage Tohya, Tsukihime, etc.
There are plenty others like Chaos Wars, Super Hero Sakusen, Capcom's cross-over series (Capcom X <something>), Gundam G Generation, etc. Too many to be said, just wiki for yourself ;P
For tokusatsu lovers, you probably already familiar with Kamen Rider Decade. A story about a passing-through Kamen Rider who have ability to pass over 11 worlds, where each world have its own Kamen Rider, and the ability to perfectly copy all those Kamen Rider's powers.
Other than that, we also have Pirate Sentai Gokaiger, Ultraman Moebius, and various yearly ritual where this year heroes meet up with last years heroes.
============= END OF WALL OF TEXT ===============
==============================================
Q1: When you pit characters from multiple different universe together, we need some kind of explanation how it's going on...
A. Hey, they all live in the same world after all...
B. There are multiple worlds in multiple different dimension beyond that gate... and guess what? We can freely go beyond and over, using some kind of mumbo-jumbo mojo or twinkling gadget.
C. There is dimensional rift and it randomly sucks people from different dimension... scary.
Q2: How do you like about original characters in cross-over story?
A. No need for them. I play cross-over to play those familiar faces I grew to love.
B. It's ok, as long as they're only there to keep the story going
C. I love them and their story should be central part of the story and their enemies are the main enemies and the main original character have power so awesome that their existence is vital for party survival.
Q3: How many original characters should show up?
A. Plenty. In fact, majority of the cast should be original characters.
B. A few. After all, cross-over doesn't need that many original characters.
Q4: How do you like with the continuity/similarities between cross-over story with the original story counterpart?
A. 100% original, those "canon" characters are indeed taken from "canon" universe, and experienced "canon" story.
B. To be kept as true as possible while altering as needed to keep continuity or integrity with cross-over universe/story.
C. A reboot (complete rewrite of the story), not the same guy/gal you used to know.
Q5: How much portion do you think cross-over original story should have in the cross-over one.
A. Big, the original characters only show up to help the cross-over characters and trip the power balance that stops the stalemate between good and evil (making it possible for the good to finally triumph).
B. None, the cross-over characters show up to help the original characters fighting against original enemies that threatening all universes and dimensions.
C. Small, somehow all cross-over enemies gathered and made an alliance of bad guys. So the good guys do just the same...
Q6: How do you like your cross-over story?
A. Dark toned, with lots of inner power strugle and gray morality
B. Brave and heroic with little consequences even when charging head-first
C. Politics, betrayal and friendship, you don't even know who your friend is.
Q7: How do you like your mojo?
A. Magic is the essence of the universe. May the magic be with you...
B. Sci-fi all the way. I don't believe anything that can't be equated.
C. Half-half. Puuuurfectly in the middle.
Q8: How many characters from each series that should show up? And how many should be playable?
A. All, all, all... mwahahaha!!!
B. All should show up, but only the major protagonist ones are playable.
C. Only two or three per series is already plenty. Give room for the others.
Thank you for answering.