CRM 2011: The server address is not valid

I recently encountered another issue with being able to connect to the CRM server using the CRM Outlook Client. While specifying the connection information I was being presented with a "server address is not valid" message.

But this message was clearly off because the Server URL and organization were clearly correct.

To troubleshoot, I enabled the Troubleshooting using the CRM Outlook client Diagnostics tool (the way to go about this is described here). Reviewing the trace file I was able to identify the cause of the error i.e. the following text appeared indicating an authentication issue:

Error| Exception : The HTTP request is unauthorized with client authentication scheme 'Anonymous'. The authentication header received from the server was 'Negotiate,NTLM'.

The resolution was simply to enable "Anonymous Authentication" to the CRM web site i.e.:

After performing the above steps, the client was able to connect to the CRM installation.