Я думаю, что я решил проблему, но я не уверен, как это произошло. На вкладке «Публикация» была ссылка на файл office.dll в файлах приложения. Он был указан в качестве обязательного предварительного условия, но не был указан в разделе Предварительные условия (именно поэтому я не принял ответ WakeUpScreaming, хотя нашел его в результате его предложения.
Поскольку в моем приложении не было ссылок ни на что из Office, я пометил этот файл как исключающий, и теперь он будет развертываться для моих пользователей.
Просто подумал, что дам всем знать, что я нашел.
Обновление от 04.06.09. После удаления всех возможных компонентов Office 2007, включая PIA, у меня все еще была проблема. Оказывается, что в GAC все еще была Политика, перенаправляющая Office 11 в Office 12, и они не будут удалены. Я использовал GACBrowser для удаления политик, и все хорошо.