We have run into similar problems in the past. A couple things to check:
1. Did the plugin mistakenly get installed twice or perhaps the 4.0 plugin was not removed disabled?
2. Does this particular user have a different Antivirus/asset management suite on their PC that the users it is working properly for?
3. When all else fails, we've found uninstalling Outlook and re-installing typically sets things right, but it's obviously not the preferred course of action.
This is of course assuming you have the latest version of the Outlook client and it matches (or is as close as possible to) the Roll Up version of the CRM client application.