During the course of that we built a lot of demos and sometimes we had to uninstall the demos. Phil Hoff from the VSTO team pointed me to the VSTOInstaller app located in C:\Program Files\Common Files\microsoft shared\VSTO\9.0. Simply point the tool at the VSTO manifest that's created by Visual Studio:
VSTOinstaller /uninstall <name-of-manifest-file.vsto>
The exception was an older VSTO 2005 SE add-in that was stuck for some reason. The last resort to at least get the project out of the list of installed programs in the Contol Panel was the brute force method with the Windows Installer CleanUp Utility.