From what I have read in other blogs and forums, this might not be the fix for everyone.

Error in Outlook:

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:
http://YourCentralAdminSite/_admin/AlternateUrlCollections.aspx

Full error:
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:
GetListItemChangesSinceToken