Outlook Requires Microsoft Outlook Express 4.01 Or Greater

[WeaponX 0]

Was trying to avoid this, but having worked with this user remotely for a few hours, I need another brain here to help out

The user was originally having problems sending emails using Outlook 2000 because it said that it couldn't find the Windows Address Book. Well, we fixed that issue but now stumbled on another one. This one was most likely caused by changing the registry value to 0 for IsInstalled. The error he's getting now whenever he tries to run Outlook is:

Outlook requires Microsoft Outlook Express 4.01 or greater. You can install Outlook Express 5.0 by running IESetup.exe from the Internet Explorer folder where you installed Outlook, or download it from the Internet Explorer site on the Microsoft Web.

This is the error message that pops up before Outlook opens. Once he clicks OK, all seems to be working again. But this is kind of annoying if he has to do this every time.
I tried to follow the instructions here but it seems to apply to Outlook Express 5 only. The user has Windows XP installed which is using Outlook Express 6. Outlook 2000 seems to be connected to Outlook Express in some way and that's why it's causing that error.

Just remembered something as I'm typing this. I actually haven't tried using one of the system restore points yet. Maybe that would help? With all the trouble we've been through, I doubt a simple restore will fix it, but we'll find out tomorrow.

If anyone has encounted this problem before on a Windows XP computer, please feel free to post how you resolved it (if it was resolved in the end).

Thanks.