Нет способа переопределить место установки ClickOnce. Как вы сказали, он генерируется во время выполнения и находится в пользовательском ClickOnce-кэше приложений в каталоге отдельных пользователей. Рассматривали ли вы наличие админов белых списков этой конкретной папки?
Полагаю, что единственный способ справиться с этим - это переключиться на установщик Windows и самостоятельно внедрить код обновления, что, очевидно, не является идеей. Внесение в белый список кэша Click Once было бы самым простым способом, но, очевидно, с учетом соображений безопасности при этом.