add-in not working through setup project

Your first two scenarios (F5 and running outside of VS) work because VSTO provides some services for your add-in in order for it to run. Specifically, it is registered so that PowerPoint knows to load it at start up and CASPOL entries are created so that it is trusted to run.

The setup project that is created when you create the project isn't complete and is insufficient to fully install and allow the add-in to run. There are two documents that step you through the process for creating a Windows Installer setup that allows end-users to run your add-ins. Part one is at http://msdn2.microsoft.com/en-us/library/aa537173(office.11).aspx and part two is at http://msdn2.microsoft.com/en-us/library/aa537179(office.11).aspx

These articles go through a lot of detail and may be more information than you need for your particular scenario (there are details, for instance, about how to set up checks for pre-requisites and language packs). But, assuming you have the pre-requisites installed and aren't concerned about language packs, you still need to create registry keys for the add-in (so that PPT can discover it) and to create CASPOL entries so that the add-in will be trusted to load. These two documents should give you all of the information you need to accomplish this.