У меня была точно такая же проблема.
Я полагаю, что ваша программа ссылается на другие библиотеки DLL, которые установщик установил в GAC или где-то еще за пределами каталога приложения. Вы не можете рассчитывать на то, что эти DLL будут установлены до того, как будет выполнено ваше действие по установке.
Решение: Создайте отдельную DLL для вашего действия по установке и убедитесь, что DLL не ссылается на другие DLL (прямо или косвенно), которые не установлены внутри папки вашего приложения.
Кстати, если можете, переключитесь на какую-то другую технологию. Я не знаю, какие конкуренты лучше, но если вы делаете нестандартные вещи, проект установки VS не вызовет у вас ничего, кроме неприятностей.