one thing I should of stated previously and it sounds like it may have been the problem.
When you open outlook you can go to the disabled items and make sure the addin is not listed as disabled. We have seen this issue as well.
Outlook 2003 you can find this in help, about, disabled items.
CommVault Messaging Support