Buenas

Como dice Javitronic, lo de formatear el disco duro es demasiado drástico, para mi, al menos, siempre lo es.
Sobre lo que te dice de agregar y volver a poner, hay un problema puesto que el explorador de windows no es algo que puedas marcar o desmarcar en agregar o quitar programas.
La solución pasaria por, segun que versión de explorer (internet explorer) tengas, pues puedes actualizarla a la version 6 o reinstalarla la version que tengas. Segun lo que hagas podras reparar lo que tuvieses o reemplazarlo por una nueva versión. El explorer usa muchos de los archivos del internet explorer (sino los mismos) y asi puedes que corrigas el error. Puedes descargar Internet Explorer de la pagina de Microsoft.
Otra solución es reinstalar Windows 98 completo sobre el que tienes, yo lo he hecho muchas veces y te mantiene todo lo que tenias sin ningun problema, y repara los archivos dañados.
Mas soluciones: en Windows 98 hay una utilidad: SFC (Save files corrupts) que se encarga de recuperar los ficheros de sistema dañados (necesitaras el cd de w98). Se ejecuta desde: INICIO/Ejecutar/SFC [intro]

Un Saludo