Hrm ... I suppose. I'm pretty sure that (AFAIK) Win95, Win98, and WinNT 4.0 all come with "Show icons using all possible colors" disabled, even on 16-bit color settings. But adding a 16-bit icon in addition to the existing 256-color version would probably be a good option to have.
It won't be that easy to add, however. NSIS really cheats when it comes to resource handling, and it makes lots of assumptions about bit depth and header structure that only work on 32x32x256 icons. This isn't a high priority item, then, but I'll try to work it in if I get the time.
And if Justin wants to try it, it would be nice if he tells us so that I don't start :P