We have found this on servers which are overtaxed as far as the ratio of services provided to hardware available and a reboot of the server fixed the issue.  Newer versions of Add2Exchange are more kind to memory, and there are ways to limit the amount of SQL memory assigned to this process.  Search for minimizing DB footprint.

The best possible procedure would be to do the following every 30 days, since both Microsoft and us put out improved versions about once a month.

Stop the Add2Exchange Service
Do your MS critical updates
See if there is a new version of Add2Exchange on the web and you have software assurance in place (open the Console and read the date in the header of the folder type).  If so, do this: http://support.diditbetter.com/kb/A2E_194.aspx

THEN ALWAYS reboot after a MS update.  If the A2E Service is stopped prior to uninstalling, there is no need to reboot after an Add2Exchange update.  To continue syncing, though, you will have to start the Add2Exchange Service.