From http://www.fjsmjs.com/OE/oeslow.htm :

Several possible causes:

Go to My Computer | Dial Up Networking and right click your connectoid.
Choose Properties | Server types and make sure that Log onto network is NOT
checked.  NetBEUI and IPX/SPX should also not be checked.

Make sure that your anti-virus is set to check program files, not all files.

Create new folders to organize your mail and move everything out of the
Inbox. Then compact it with File | Folder | Compact while in the Inbox.

If you have (or ever installed) McAfee 4.03 extract imagehlp.dll from the
CAB files and put it in C:\Windows\System.  If you installed or updated
IE/OE from the Microsoft pages you should find it in SETUPW95.CAB in
C:\Windows Update Setup Files.  This problem may only occur if you upgraded
from an earlier version of McAfee.

For some users, mostly on WinXP, when they remove windows messenger or just
disable it from starting up automatically they experience a great slow down
when launching Outlook express. Users who experience such a slow down will
find a error in the system error log saying The server
{FB7199AB-79BF-11D2-8D94-0000F875C541} did not register with DCOM within the
required timeout. The solution this problem is quite simple. Just Open up
Regedit and search for the string

{FB7199AB-79BF-11D2-8D94-0000F875C541}

and modify the keys InProc32 and LocalServer32 default key to a empty
string. After a reboot, Outlook Express will start up as quickly as
possible.  See:

http://www.tweakxp.com/tweakxp/display.asp?id=108

If none of those fix the problem, rename pstores.exe, psbase.dll,
pstorec.dll and pstorerc.dll, then extract new copies from the CAB files.
See http://support.microsoft.com/?kbid=251787 .  This KB article includes
instructions for repairing the Protected Storage Service under Win2K and
WinXP:
http://support.microsoft.com/?kbid=264672

Another thing that has been reported to help is to click Tools | Internet
Options in Internet Explorer.  Go to the Advanced tab and scroll down.  Make
sure that Use SSL 2.0 and Use SSL 3.0 are checked.

See also:

http://insideoe.tomsterdam.com/problems/performance.htm