They don't have to not transition smoothly, but they can be much quicker, or rather than fade to black, do a crossdissolve between the two clips if they have similar colors.
It's kinda hard to point it out, it just depends on what's going on. If you have for instance, an obvious point in the music that lulls and then starts up suddenly, you could have one clip fade to black and then have the next clip rush in with from the black but hike the bloom/glow up and have that fade quickly into the normal clip, like in half a second.
The reason I tend to use a lack of transition is that for melee, it's hard to pick a good one in the first place.
With things like an fps montage, it's very easy because lots of things on the screen are constant no matter what the situation, like the gun/HUD. With smash, the colors vary a lot, the placement and size of the characters change constantly (not physically, but the camera moves in and out).
Ie in an fps video, you could do something like, make a good play, and then rewind the footage quickly to the beginning, where a similar clip starts with a different play. In smash even if the play is identical, the chances of the camera, background, and placement of the characters makes this really difficult to pull off with the same feel.
An fps player, can also do things like make tiny bits of theater, watching the player in 3rd person or free cam, leading up to the shot or whatever.
So smash videos really don't have much to work with. If you really want things to be smooth without making the video generic or slowing the pace significantly (generally bad in smash, because how often do you have a slow combo?) you're going to have to make sure each clip has something that ties it into the next clip. Doing that on top of syncing to the music without significantly altering the speed of the clips, tends to be pretty difficult. If there's no transition, you can focus entirely on syncing, and like I said earlier, depending on the music the suddenness can be good. It's also partly that I've never sat down and focused solely on the editing in a video I've made. It's usually just collecting and placing all the footage that takes time, and I've never had the desire to spend a ton of time on the video, and good transitions/editing are something that will take a lot of time for a smash vid.
If you really really want smoothness, but also don't want to put a ton of time into each and every transition, just do a combination of crossdissolve (additive works pretty well sometimes) and dissolve through black like you've been doing, but speed up the transition. It'll still be smooth if you halve or even quarter the length of some of those.
An example from your vid, looking at the clip that ends around :44. The main melody kicks in with the guitar, and the death should be taking place when the guitar slides down the neck (not sure what the term for that is) right before the next measure and have the transition be concluding on beat with the next clip. Clip needs to start on the beat or a significant note in the music, but it doesn't instead you still see falco running around for about and then link starts things up after the music's already hit the fan. In this case I would have liked a lighter colored stage to be in the next clip, dreamland or yoshi's would be good. I would probably use an additive dissolve in this case because it won't get too bright because of the black background in the second clip, and maybe a little flare to accentuate peach's death. In terms of timing, I would like to see link's bthrow animation happening on the beat, meaning the grab is happening on the upbeat to the melody.
If you want I can try to make a video that focuses more on editing/transitions than actual footage to show you what I mean, and annotate it, to the song of your choice. I would try to do it based on the footage in the clip, but the fades are already there, and getting stuff directly from you would be a bit of a hassle
edit:
actually this video I did recently
http://www.youtube.com/watch?v=KCv9nAWTvEs will work. I'll put up 2 more versions of that. The current version is light on editing, but the timing is good. I'll put up one version with those transitions all fade, and one where I put some work into it and try to spruce up the editing. Sadly, some of the footage in that is choppy, but I have it sitting out still as a project so it'll be easy to pick up and change.
also I really wish TRC hadn't turned into into something dumb/gotten canceled as an anime. I enjoyed the manga, I think if they had stuck completely to the story for an anime it would have been great.
for music, I prefer instrumental tracks as well, nowadays, but vocals work to your advantage occasionally. I'll give the music some more thought.
I hope some of that helped or else I just wasted a bunch of time haha. hit me up on aim sometime, it'll probably be easier that way.