Это проблема :)
В любом случае, инстоллер - это нечто более серьезное, чем просто склепанный на коленке msi :) При этом, что интересно, фирмы зачастую этого не осознают :)

Ну с реестром проблем нет, если это HKCU :) В HKLM в Висте и Windows 7, по дефолту, писать могут только администраторы (ну и те юзеры, которым дали соответствующие права)
С Program Files таже история :)

Все зависит от программы, в принципе можно в манифесте указать, что программа требует административных прав и тогда все будет ОК :)
Ну вот только у пользователей с админскими правами будет соотщение от UAC'а (если он включен), а у неадминов будет предложение залогиниться админом :)
Надеюсь речь идет о какой-то серьезной программе, а не об mp3 плейре

Зачем тебе вообще батник? Тебе мало удаления через ARP?

Книжку надо по MSI прочитать, а смена инструмента ничего не даст. Гвозди можно забивать и газовым ключом, и молотком, и топором и даже лопатой :)

Одно некошерное рещение заменяете другим :)
Не думаю, что пользователь будет рад тому, что его заставляют в новой версии программы по новой устанавливать все настройки :)
И второе, кто тебе вообще сказал, что оставлять данные после деинстоляции плохо? :)
После деинстоляции можно, и в коммерческих программах даже нужно, оставлять данные :) Иначе такие вещи как тестовая лиценззия на Х дней просто не будет работать ;)