I do have two in mind I personally think are perfect for Wario; however, I'm saving those for myself, so... only if you ask reeeeallly nice would I tell you what they are
I think it can be called hardcore techno, Powerman 5000's Drop the Bombshell you might like if you put Dethklok to the preview
http://www.youtube.com/watch?v=K-SQ4GbL7Hc&feature=related.
I just reeeeally wish we could get Wario's theme from Strikers Charged available as a full track, that Hungarian Oopma or whatever it is is just so awesome :D It sounds evil and fat just like Wario. The closest we can get is this:
http://www.youtube.com/watch?v=4ChMW4wMz3Q. At 1:14 you'll know what I mean when I say it's not full... (you can also hear some of it in his entrance, the same guy has it; it's the best one Wario sings along to it :D)
....thinking along the lines of something sinister and heavy-sounding to fit Wario, I've come up with these: In the Hall of the Mountain King
http://www.youtube.com/watch?v=CjFlNKdZSM0, and Assembly Line Apparitions
http://www.ocremix.org/remix/OCR00980/ (hey there was a kirby melee combo that had DKC2 remix in it, so why not lol)
Also to add to my suggestions would be System of a Down, they've got some great stuff if you want to work it in, depending on exactly what you're doing in your video. For example, I chose to use Aerials to go to a mm video of me as Jiggly vs. my friend's Zelda; aerials in the sky indeed.
The band is called Lesiem, it sounds like all their stuff is latin, so that might warrant further investigation.
