During a recent job, I created another user profile with the intent that the second profile would use Outlook with different email credentials. However, during the setup process, Office 2007 failed with several errors. Then when I rebooted and started Outlook again, I got an error that "mapi was unable to load the information service mspst.dll".
First off, there is no mspst.dll. The file that is causing the problem in my case was mspst32.dll. There are several links that suggests that it is in the system32 directory, but that's not the case. It's actually in Program files\Microsoft\Office 12\. There are several comments that reinstalling didn't help or that in some cases it did help. There is also the common files directory which holds the mapi settings for Microsoft mail in the \common files\system\msmapi\1033 directory and one thought was to rename the msmapi.dll file in there. That does cause Outlook to reinstall that file, but it didn't fix the problem.
I downloaded some bogus copy of mspst32.dll (by bogus, I mean a file offered by a .dll download site) into the system32 directory, but that didn't change the problem. Finally, when I realized that there was a copy in the program files directory, I deleted the one I copied into the system32 directory and renamed the one in the program files directory. Outlook reinstalled the correct version of mspst32.dll and outlook started up fine.
This problem forced me to troubleshoot it to solution because the corrupted mspst32.dll file also broke outlook for all users on that PC. I didn't want to reinstall because I'd lose the user settings. Once the correct mspst32.dll file was loaded again, both accounts worked without further problems.