Actually there's no way you could lose IE altogether unless you try pretty hard. Check these links:
http://support.microsoft.com/kb/293907/en-us
http://www.stopie.com/removingie/ and see if reinstalling IE solved your problem. You'll need to have IE at least for configuring your automatic updates at
http://update.microsoft.com/microsoftupdate/ .
Check this one out for restoring toolbars, I haven't tested it myself though.
http://www.dougknox.com/xp/utils/xp_toolbarfix.htm .
Does Start - Run (write "iexplore" ) work for you?