good suggestions, I'm looking at the glue gun stuff but I'm a little concerned about the implications this could have for the map design as a whole. it feels like it'd be more central to the game.
I'm sure Vanillaware's techniques and technology are far beyond anything I do. What I do is all in photoshop, I'll figure out the poses and movements by traditional means and/or manipulating body segments, and then retouch over them to make it all look good. Sometimes I'll rough out an animation idea and then build up the detailed body parts piece by piece like I'm building up a structure. So, I imagine it's the same basic idea at play as what VW does, but much less sophisticated.
This is my old run animation from the old game.. It's a bit lower res because I only ever expected the character to be rather small on screen. As such it's a little messy looking because the small size hid any warts.
What I'm working on doing now is fixing up the pose and proportions a bit (not quite happy with them), longer, better looking cloth, blowing it up to a higher res and retouching it, and generally rebuilding the same animations but doing it better and adding new ones as well, such as connective transition animations. Also, the aforementioned "left-right consistency" (as opposed to flipping the sprite left and right).
The original animations, as seen above, while they took a lot of effort, were always done with a certain "well, I'll let that slide" type of laziness because it was "just" a flash game. The approach is a bit more thorough now. It's a big job, and it'll take me a while, but I think the end result will be worth it. A good visually compelling main character is essential to this type of game especially if you want to stand out.