Also, I would not uninstall Outlook just yet. Doing so may remove the MAPI Subsystem from your Exchange server and pretty much ruin it.
Outlook uses a client version of MAPI, 1.0.xxxx, and full Exchange uses 6.5.7638.1. Right now after installing Outlook you have now made the Exchange server use a client version of MAPI which does handle server side requests.
I am not sure if there is a fix other than reinstalling Exchange but I would possibly contact Microsoft if you can't find any other way around it.
If you're Exchange server is that important you could always export your mailbox to a PST, reinstall the Exchange and import the data from the PST back into your new mailbox.
Also, what account did you use to install the BES? Did you create the BESAdmin account?
If not then follow this article to do a switch service account:
BlackBerry Search Results
The BES needs to be installed and used by an account with a specific set of rights/permissions. Even though a domain admin sounds like it will work, it won't. That account will cause calendar issues and also a possible sending issue after certain updates are applied to the Exchange server.
Follow the above article the BESAdmin account but I would look into moving the BES to a new server. Seeing as nothing is working as of yet I would start fresh, new database and all.