From what I have read in other blogs and forums, this might not be the fix for everyone.
Using Fiddler, I was seeing the same reference to http://randomSite.SP.com.
In my case, it turned that I had an outdated / not used URL in my Alternate Access Mappings.
Default Zone was set to http://goodSite.SP.com
Intranet Zone was set to http//randomSite.SP.com
Once http://randSIte.SP.com was removed, the Outlook error went away.
(removing the mapping did NOT induce an IISreset.)
Alternate Access Mappings can be found here:
Task ‘SharePoint’ reported error (0x80004005) : ‘An error occurred in this SharePoint List (site name – list name). Try updating the folder again. If the problem continues, contact the SharePoint site administrator. HTTP 500.
The server returned the following error message: Exception of type
‘Microsoft.SharePoint.SoapServer.SoapServerException’ was thrown.’
Fiddler referenced this web service: