Startup time has nothing to do with the installer. It's a function of how
long your addin initialization takes plus various overheads for managed
code.
If your addin is the first managed code application to run in that Outlook
session the CLR has to be started up. Your addin has to be JIT compiled and
put into the cache if it wasn't already JIT compiled and in the cache. Those
operations take some time. You should notice much faster startups if you
close Outlook and then re-open it right away while the addin is still cached
and the CLR is running.
For VSTO addins there's additional overhead of starting the VSTO runtime.
If the registration of things such as COM addins or form regions isn't
working you need to see what's different about where it works and where it
doesn't. User installation rights, permissions on different sections of the
registry and where the addin is being installed (HKCU or HKLM) must be
investigated. In general VSTO addins require admin permissions to install.
For VSTO addins you also have the consideration that the assemblies must be
strong named and must have full trust to run. You need to check whether or
not the CASPOL settings for full trust have been applied to your addin
assemblies.
You also need to check the Fusion logs to see what's failing to load and
why. See
http://blogs.msdn.com/vsod/archive/2008/04/22/Troubleshooting-com-add-in-load-failures.aspx
for information on how to do that.
Your problems most likely will not be solved by switching installer types.
They will haunt you with a setup project installer until you find out why
your current installer is failing in some cases or why the loads are
failing.