1. Попытайтесь получить лог установки, используя эту статью. Если получится выложите здесь.
2. Важно, чтобы развёртывание запускалось напрямую с сайта. Для этого постарайтесь использовать Internet Explorer или EDGE.
3. Установка зависит от некоторых условий окружения при запуске. Прежде всего это наличие или отсутствие Framework .NET на машине развёртывания, а также важна версия библиотеки Microsoft Visual C++ 2010 x86 Redistributable. Поэтому идеальный вариант установки - это отсутствие какого-либо предустановленного софта из указанного. Вот почему Вам удаются установки на "чистую" виртуальную машину.
4. После использования ClickOnceUninstall не лишним будет очистка папки: C:\Users\%USER%\AppData\Local\Temp.

P.S. Если ничего не поможет - пишите в ЛС предложу другой вариант помощи.