Oh, no not all the palettes have to have black. The only requirement is that all of them have to have the transparency value, creating the NES' max color limit of (3*8)+1=25. (4 palettes for sprites, 4 for environment) In theory you can do anything with these 4 palettes, but the way Rockman is setup demands such things as the player having a palette solely his own, the face palette being around at all times. Similarly, almost all the sprites have a black outline in Rockman games and palettes are heavily interlinked between different objects, which is why practically all palettes have it.
Now, in theory you can also make any and all outlines using just the face palettes, but then you'd have to be overlapping two whole objects at all times. However, there's a practical limit of 8 sprites per scanline, 64 on screen, so you have to have a black for the outline in each palette to reduce the sprites on screen.
In very few cases the black value can be changed to something else. The biggest example being the mugshots, which are a combination of sprites and tiles, and thus often use and altered face palette that instead of black has an extra skintone.
Anyway, here's a visual example of boss palettes and how they relate to the player character:
