I just checked the mapi32.dll file on the servers, and on bes the version is 6.5.7888.0, and on our exchange the version is 1.0.2536.0. Now I'm pretty sure that's bad, but I'm not sure if I should take the BES version and put it on exchange, or take the exchange one and put it on BES.
Yes, MAPI 1.0 on your Exchange is very bad. MAPI 1.0 is a client version, Outlook essentially and it doesn't usually handle server side requests well. DO NOT
copy and paste MAPI32.dll ever!!!!! It's a more than just a file, it's a subsystem. Copying/pasting and registering will not fix that issue. I would check some Exchange Forums or contact Microsoft to correctly fix that. If that was BES you could apply the latest Exchange Service Pack. That might be possible here as well, applying the latest Exchange SP, even if you have it installed already, should update the files accordingly.
It also sounds like you ight have installed the ExchMAPICDO.exe from Microsoft on your BES. Is this Exchange 2007? If so, that's fine.
If not, install the Exchange System Management Tools on your BES from your Exchange CD and apply the latest service pack. That should get your versions to match.
I would look at correcting the Exchange side first. Rule out everything else but the BES first.