Jet A1,
Not really.
What software did you remove?
Is this XP home or XP Pro?
Where the Icons on your Desktop, Start Menu or All Programs Menu?
Exactly which Icons are in question? Where they all just related to Internet Explorer or are there others?
Did you right click on them, go to Properties to see if the Icon was there? Did you try from within Properties to click on Change Icon?
I just need something to go on, so I do not have to get out my trusty old dart board.
Take Care,
Richard