Are you deploying ithe Add-in using a setup program?
If so, did you follow the steps shown in the link:
http://msdn.microsoft.com/en-us/library/aa537179(office.11).aspx(the section "Walkthrough: Enhancing the Outlook Add-in Setup Project")
The project SetSecurity contains the custom actions that do all the security settings for you. I used for an Excel Add-in and it works OK.