Oh, there was one other problem I had years ago with OE taking minutes to start up. Somehow the "protected storage" service had got turned off and OE spent a long time timing it out. The symptoms of this one are that you double click on the OE icon (or whatever) and nothing at all appears on the screen for minutes. (I had to use the debugger on this one to get to the bottom of it, all in binary of course as I don't have the sources; it took hours.)
If OE's window opens up as usual but you just can't do anything with it for ages then my money's on McAfee.