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")
Please post your registry key located at:
HKEY_CURRENT_USER\Software
\Microsoft
\Visio\Add
ins\
ID>
so we can check that your Add-In has been installed correctly.