Explorer and Outlook Express wont connect

[needhelp]

I ran BeClean on my other computer to clean out unwanted files and this went okay and the computer ran okay after that, but after I shut it down and rebooted, Internet explorer and Outlook Express will not connect to surf or check emails.
I have used BeClean on my other computer and have had no problems. I ran the BeClean restore function but no luck. I can connect to my provider okay and ICQ connects and works okay, but not Explorer or Outlook Express.
I thought the easiest way to fix this would be to reinstall ME over the top so that Explorer and Outlook Express would be reinstalled but still no luck. I guess the reinstall only replaces files that are missing not corrupt files.
The rest of Windows seems to be working fine.
I contacted my provider and had them check things out, Internet settings etc. and did a ping test and verything was okay from that end.
They suggested the only way to overcome the problem was to format the hard drive.
I didnt really want to do this cos the drive has only the one partition and lot of work to back everything up.
My version of ME installs Explorer 5.5 by default and I was wondering if the problem might go away if I was to install explorer 6 which also includes Outlook Express 6 or will I still get the same problem.(I have explorer 6 on a separate CD)
I tried to do the ME restore, but as per ME, it doesn't work when you need it.
Any suggestions?

[Redo40]

You might try doing a repair on Internet Explorer first, but upgrading to IE 6 will most likely fix it.

[Dan]

first, I don't recommend reinstalling software when there is a problem...this can cause more problems.
If you are able, I would try restoring the registry to a date before this all happened.
f8 at boot, command prompt, type (where "c" is your hard drive) C:/scanreg /restore (space after scanreg)
just choose a date before the problem arose.....