This is sort of a longshot, but if you have disabled/uninstalled Windows Messenger (not MSN Messenger) Outlook Express will open slowly because it is trying to automatically start Windows Messenger, but can't find it (because it ain't there). The reason it takes so long to realise is because it has a timeout limit which must be reached before it gives up trying. The way to fix it involves a little bit of registry editing, so you might want to make a backup if you are worried about making a cock-up hehehehe.
Press Start > Run... then type regedit into the box, and click OK. Navigate your way to the following key:
HKEY_CLASSES_ROOT\CLSID\{FB7199AB-79BF-11D2-8D94-0000F875C541}
(To make a backup simply right-click on the key and choose Export, then save it somewhere where you will be able to find it again.)
Expand that key, and there should be a couple of sub-keys within it. One or two sub-keys should be labelled LocalServer32 and InProcServer32. There's a good chance that one or the other won't be there, but don't worry if that's the case. Single-click on the first one, and in the right-hand panel you'll see a string labelled (Default). Double-click it, and remove any information that's in it, and click OK. Do the same with the other sub-key I mentioned. Close the registry editor, and maybe you'd be best to reboot the computer. Try opening Outlook Express again and see if it has made any difference. If not, well, at least you've eliminated one other possibility ;) If you don't notice a difference you might want to import the backed-up registry keys again. All you need to do is double-click the registry file you saved and select "Yes" when prompted if you want to add it to the registry.
If it doesn't help I'll eat a pooh-sandwich as compensation.
Good luck :)