For software that Microsoft provide with Windows, you generally need to look in "add/remove features" (within the add/remove programs control panel).
However, if you used some third party tool (Revo ?) to uninstall a core element of Windows whose uninstall is not supported (not saying this is the case with OE, have not checked yet), then you're on your own. Because the Windows Update process won't be properly setup to look if something exists when it's looking for it to be there given that it's uninstall was not permitted in the first place.
So, I think the first thing to establish is whether removal of OE was permitted in the version of Windows you are running. And if so, to rack your brains as to whether you did it the supported way, or just threw your third-party uninstaller at it and hoped for the best.
Have you also tried creating a new user profile and seeing if you can replicate the problem there. You may have just messed up your usual profile and got Windows all confused.
Hope this makes sense ?