I had this exact same issue for one of my users last year. I moved her mailbox to another store and it seemed to have fixed it.
Another thing you can try if this does not resolve the issue is a little more complicated and has to be done on the client end. Open their Outlook profile, then FIRST create an empty pst file on the folder list [Do an export to a pst file, select the top level folder, named mailbox (username) and do not select to include subfolders], next right-click your new pst personal folder and add a new folder and make it a calendar, then go the their calendar then go to view, choose current view and select “all appointments”. This will change the calendar to a table view. Click inside the table view pane and select all, then right-click and choose “move to folder” and move all the appointments to the pst calendar on the folder list. Moving the appointments in this manner preserves all the recurring appointments and keeps them linked together. After moving them out, reverse the process and move them back to the original calendar. For some reason this clears up corrupted calendars and I have seen it resolve several odd calendar issues.
To move mailbox to another store, do I need to contact Office Live since they are the email provider?