Example (and I'm not saying they were the first, I know they weren't), WinXP has 24-bit icons now rather than 256. The icons do look better. XP also now allows humungous-size icons, like AmigaOS has since the dawn of time. Are you telling me it wouldn't notice on any large icon at all either?
And yes, some images can be scaled down to 256 colours without noticable loss of quality. Anyone who does sensible web design knows this.