Assume that this only happens when he has Outlook opened and running on his desktop.
Check a couple of things:
1. Open Outlook with the switches applied to rebuild his folders and views and to reaply the Free/Busy time:
(Example: "D:\Program Files\Microsoft Office\Office\OUTLOOK.EXE" /resetfolders /cleanfinders /cleanviews /cleanreminders /cleanfreebusy)
2. If that still fails try removing the Outlook Profile completely and then recreating. You may need to delete his profile files before recreating. Location depends on OS version, but typically found under \Application Data\Microsoft\Outlook
If the problem still persists and/or the problem is apparent no matter if Outlook is opened or not. Then you may very well have a problem with the datastore, which means you will need to take the IS Service offline and use the ISINTEG with its repair switches against the private store.
If you have another server in the site, try moving the user to the other server to see if it clears. If it does you do have a minor problem in the original location and it should be fixed.
Good luck