I found the answer, after hours of research. Megaman games use 25 colors. "Wait what?!" is what you're thinking right? There are many opinions on the internet about the NES's color limits, and most of them are dead wrong.
Here is the truth I discovered.
The NES has 8 palettes total. Period. There is no way to increase this number, not even with extra chips in the cart.
Each palette consists of four colors. Only THREE are visible. There is NO exception to this rule either. There are four background palettes, and four sprite palettes.
(4 background palettes) x (3 visible colors) = 12 colors
(4 sprite palettes) x (3 visible colors) = 12 colors
12+12 = 24 colors
But wait, that's not 25! You're right. There is one more color, that is the full screen background color. Usually it remains black, giving the background the illusion that there are four colors per background tile.
So, that makes up the full 25. So why do Megaman games usually have 17 colors or less?
Sprite Palette #1 (Megaman's body)
(transparent) (black) (blue) (light blue)
Sprite Palette #2 (Megaman's face)
(transparent) (black) (skin) (white)
Sprite Palette #3 (Enemy 1)
(transparent) (black) (color1) (color2)
Sprite Palette #4 (Enemy 2)
(transparent) (black) (color1) (color2)
Notice that black is in every palette. Anything that uses these palettes needs to be outlined, right? Well, that's 4 colors right there. Even though they're duplicates, it counts toward the 25 total. This is how Megaman games don't get above 17. Its not that they decided not to, its that they really couldn't. A lot of enemies and effects reuse Megaman's face palette. No enemy uses Megaman's palette though, because it changes with weapons and charging.
This example is ditto for background palettes. The same logic applies.
Depending on what enemies are on screen, and between rooms, these palette do change, and they change very often.
So, that's mystery solved.