Reinstalling the service packs are fine but I don't think they will solve the problem. The dll may have become corrupt, unregistered or possibly removed. MAPI32.dll is used by a few programs, Outlook and Exchange Client (exchange client is installed with the Exchange Admin I believe) are two of them. Have you recently uninstalled Outlook or any other program that may use MAPI32.dll?
Do a search on your system that is having the problem and see if there is a MAPI32.dll file present under /winnt/system32. If the file is missing reinstalling Outlook or the Exchange client should recreate this file.
If the file is present then it may have somehow become unregistered, click on Start-Run and type in this to register the dll: regsrv32 MAPI32.dll
This should return a popup window that says that it was successfully registered.
If it fails to register then it could be corrupt. Rename the existing mapi32.dll (which if the dll is in use won't work, so load the system up in safe mode and don't load up exchange admin or outlook) to mapi32.old and then reinstall outlook or exchange admin to replace the file with a new one.