Microsoft Dynamics CRM 4 for Outlook cannot be installed on a computer where Microsoft Exchange Server versions prior to Exchange Server 2007 are installed
I got this error while trying to install the outlook plugin for Microsoft CRM on a terminal server. The terminal server was definitely not running Exchange.
To fix this you need to get rid of a key in the registry.
You can export it, do the install and import it back if you need but it needs to be gone for the install to work.