Win2K SP3 adds the ability to "hide" access to IE, Outlook Express (OE), and Media Player, or to "disable" them completely. This is a feature designed to permit system administrators to prevent people from "finding" them, or to prevent them from using them altogether. This capability is not present in previous versions of Win2K.
This isn't something you would be likely to have elected during an install of SP3 - unless you poked pretty deep into the settings and did a manual install instead of just taking the defaults. If you elected to "hide" these, you would still be able to get to them by displaying hidden files and going directly into them, but it might prevent desktop shortcuts from working - I don't know for sure.
If you still have SP3 installed, you can check on the settings that do this stuff. Instructions are in the Knowledge Base article 324644 at the link below.
If, for some reason, you "hide" or "disable" access to these programs, and then remove. (or attempt to remove) SP3, the ability to change the hidden/open or access/no-access abilities are removed, and you cannot restore access to these programs.
The fix is to reinstall SP3, and change the properties for the programs to whatever you want. Once they are accessible, you may remove SP3, although I see no reason why you would want to.