Bien, pues damos el tema por solucionado.
Evidentemente el explorer no lo tenías que eliminar

, simplemente esta entrada que hace referencia a él para que no cargue en el inicio, ya que eso no es normal:
O4 - HKLM\..\Run: [IEXPLORE.EXE] C:\Archivos de programa\Internet Explorer\IEXPLORE.EXE
Pero nunca eliminar el archivo IEXPLORE.EXE.
Saludos