I've seen this happen on a number of occasions. Users are happily syncing away using their Salesforce side panel in Outlook and then one day the side panel is not there.
Here's where to look:
(This is in Outlook 2010, other versions will have similar options)