So you really removed MAPI32.dll, removed all of office, reinstalled office, and you still get the problem? Then I'm really not sure what is up. It sounds like there are leftover registry issues. When you go to Add Remove programs was everything from Office really gone (like Office 2007 Primary Interop Assemblies, etc.)?
I'm not sure what else to try. I have heard of this program:
Download Remove Office 2007 1.0 - Clean uninstall of Microsoft Office 2007 - Softpedia
that is supposed to go a good job of cleaning up the registry.
I do know of another user on this forum who said he deleted MAPI32.dll and reinstalled office and this exact problem went away.