A co-worker of mine recently complained that his IntelliSync synchronization was failing when trying to sync over 11,000 records when he was syncing his calendar. After looking into the issue I discovered that the IntelliSync engine examines both the activity and history tables in order to determine if the Outlook calendar item is still scheduled or has been completed.  The problem is in the query IntelliSync is using to scan the history table.  it is essentially this:

select * from history
WHERE ACTIVITYID is not null and
TYPE in (262146, 262145, 262162) and (not (PRIORITY = 'ISYNC_DEL') or PRIORITY is null) and USERID = 'THEUSERID'

For a user who has years of history this can be a big problem, since there is no date restriction.

To solve his particular issue, what we ended up doing was clearing out the ACTIVITYID from the history records older than 1 year.  This then dropped them out of consideration of IntelliSync and his sync went from hours to a few seconds.