Quick tip: Sometimes running FIXMAPI.EXE doesn't solve the "Cannot start Microsoft Office Outlook MAPI32.DLL is corrupt or the wrong version. This could have been caused by installing other messaging software. Please reinstall Outlook" error. If it doesn't work for you, try renaming the MSMAPI32.DLL file to something like MSMAPI32.OLD and then restart Outlook. Office's file protection should then copy the correct DLL into place and all would be right in the world. It's then safe to delete the .OLD version of the file.
For English based systems, the MSMAPI32.DLL file is living in %programfiles%Common FilessystemMSMAPI1033 folder. Other locales will be in a numbered folder other than 1033.
We ran up against this when a client got a computer with a 60 Day Trial of Office 2007 on it, but installed their corporate version of Office 2003 over it. Uninstalling Office 2007 presented the error.