Recently I was setting up CRM for Outlook client on a existing environment that we took over. CRM for Outlook would always display the following error after entering the organisation url details in the configuration screen.
The underlying cause seems to be the underscore character in all the crm service urls. The relevant KB316112 article says:
Since CRM for Outlook cannot set the cookies, the client cannot be configured.