Really nice stuff all round. Delkaes has too many palettes. Should be easy to fix. Could use a bit of mechanical elements just to create that weird techno-organic feel that's very prominent especially in the MMX games.
@ Waltuo. Checking out some megaman sprites, it does seem like a waste to include black in most palettes, so maybe it would be a good challenge to make that NES X without black outlines and separate him from BGs by other means.
@ Mt® awesome mockup. The health bar uses megaman's face palette in the games. If you include mega-blue in the health bar it will flash when you charge the shot and it's a bit of a waste to overlay sprites in the health bar.
Here's part of my artilleryman stage.

The orange cannon is mostly BG tiles while the grey parts are sprites. When you blow it up, the small guy comes out BOING BOING.