Just go to Run and insert this: %windir%\ie8\spuninst\spuninst.exe
If you do not find SPUNINST folder under C:\Windows\ie8
Please copy the same folder structure from another server and run spuninst.exe.
It would probably as some files that may be required to uninstall, as and when it asks for a file find the file in another pc and copy it on to the PC.
IMP: IEENCODE.DLL.000 file is required.
I could not find this file any location.
What i did was, i copied the IEENCODE.DLL file to another location and renamed it as IEENCODE.DLL.000
and feed this file when uninstaller asks.
done.. your IE 8 is uninstalled successfully!