Want to completely remove ie8 and reinstall afresh.

Check this:

http://support.microsoft.com/kb/957700/en-us

Try typing this command on the command prompt (Start > Run):

%windir%\ie8\spuninst\spuninst.exe

Select allOpen in new window

Alternatively, there is a link to an automatic removal tool (Fixit) on this page:
http://www.thetechhub.com/2009/03/how-to-uninstall-ie8-on-windows-xp.html

Should you encounter a problem, then this could be related to Service Pack 3 having been installed after installing IE8.
In that case, you first need to remove SP3, then uninstall IE8, then reinstall SP3, then reinstall IE8. Reboot once before reinstalling.
Sorry for the complications, but that is Microsoft.

Hi, I have followed that instruction, but I still can not see the icons for ie8 in my start menu or in program files. How can I resolve this?

Check the follwoing article at Microsoft's site, it entails everything about fixing the IE8 as well as reinstalling it.

http://support.microsoft.com/kb/318378

>>  "Hi, I have followed that instruction, but I still can not see the icons for ie8 in my start menu or in program files. How can I resolve this?"

This is unclear. Which of the instructions given before your comment did you actually follow? And is it that you reinstalled successfully, but cannot find the program shortcuts for IE8?
If you do: Start > Run > iexplore.exe
- does Internet Explorer launch? If so, which version of IE is that?

Even though ie8 was fully installed (ie9 is only for win7 or vista), in the add remove windows components in add remove programs was the issue here and edbedb allowed resolution.