On the machine which you are deploying to, the first thing was (I didnt realise probably because I didnt read the instruction manual closely enough) that you must install the VSTO2005 SE run time, however you should only do this after you make sure that the Office PIAs are installed. Apparently this is because the VSTO2005 run time updates one of the Office PIA DLLs. You should also initially make sure that dotNet 2.0 is installed otherwise VSTO2005 SE wont run.
The next issue is to get your custom DLL trusted by dotNet. This is a lot easier said than done.
Identifying the problem
The first problem I had was actually finding out why my Outlook addin would run. It would run fine on my VS dev. machine, however Outlook just kept disabling it. I found a really helpful forum post here which says that if you set the environment variable VSTO_SUPPRESSDISPLAYALERTS to 0 (zero) then VST will display all errors that occur during startup. You can also get the errors logged to a file by setting the environment variable VSTO_LOGALERTS variable to 1 (one). This creates the log file in the folder that contains the application manifest. The default name is .manifest.log. (See MS Article Debugging in Application-Level Projects)
Debugging the problem
The startup error I found was "Failed to grant permission to execute." Basically this means that dotNet is not trusting your assembly on the deployment machine. (Note: once Office starts with and Addin error, it helpfully disables it for you. To re-enable it update the registry key HKCU\Software\Microsoft\Office\Outlook\Addins\youraddin.connect\LoadBehavior = 3. After a failed load Outlook will have set it to 2)
To enable security on the DLLs, there is an MSDN article on adding a SetSecurity project to your existing project (available from MS here). You then update the setup deployment project for the custom action data for the Install method (full info here)- I couldnt get this to work.
Some people suggested trying to bypass the windows CAS and give enough security-level to the addin. You could use CASPOL or add the assembly to the GAC (dragging and dropping it at c:\windows\assembly) - however I cant get either of these to work in Vista. Adding the assembly to the GAC on XP fixes the addin load permissions problem. (To add your assembly to the GAC you will need to sign it with a key in VS2005 to make it a strong assembly).
So after more than a days work trying to deploy my Outlook addin - I have a workaround with XP where I can use the GAC and have made no progress on getting it deployed using SetSecurity or on Vista!
Deploying Visual Studio 2005 Tools for Office Second Edition Solutions Using Windows Installer
Visual Studio Developer Center - Debugging in Application-Level Projects
Microsoft .Net Framework 2.0
Microsoft Office 2007 Primary Interop Assemblies
Microsoft Visual Studio Tools for Office 2005 Second edition runtime