In your startup menu look for the IE icon and right click. You will get a
popup menu with several selections, go to "send to", and then click desktop.
If you have the quick launch toolbar showing you can do the same thing from
that IE icon. To show the quick launch toolbar- right click anywhere on
your taskbar, in the popup menu go to toolbars, check "quick launch".
Use Control Panel's Add/Remove Programs applet.
Click on Add Components and put a checkmark beside
Internet Explorer. Note the Description under the list
when you have selected it...
Description: Adds or removes access to Internet Explorer
from the Start menu and Desktop
(You probably thought you were removing IE in the old Win9x sense
when you unchecked it.
BTW if you are just after an icon you could probably create one
with right-click, New Shortcut, etc.