Yes, OE is installed with IE, but it can be "uninstalled", only meaning it can be made to appear to be uninstalled by being invisible. In Add or Remove Programs, Add/Remove Windows Components, OE is one of the programs that can be uninstalled or installed. Again, the underlying files are not actually removed.
That's what I meant when I asked him if he had it installed. Indeed, I think uninstalling OE via Add/Remove Windows Components and reinstalling it might possibly fix this. I'd give it a shot.