ITNinja

If a key file is found to be missing on launch, Windows Installer will trigger a reinstallation of the parent feature. Having a "clean" package is key.
To find out just what the problem is, look in your Application Event log. Or for more detail, turn on Windows Installer logging and search for the word "error" in the resulting log file (found in %TEMP%).
Some common reasons why this may occur:
Missing Files or Registry Keys
Look closely- some files are deleted by the application itself. If your package contains such a file it will self-heal in order to restore the file each time.
Temporary Files Included In MSI
If any temporary files left on the system are captured in your package, they may cause self repairs to occur in order to restore them.
HKEY_CURRENT_USER Keys in Package
HKCU Keys are installed only for the current user. Therefore, the first time the application is run by each user, the HKCU keys belonging to the package will not exist resulting in a reinstallation of the containing feature.
Are you creating your own package?
Make sure your package does not contain anything it should not using a product such as PackageCleaner.
Yet another possibility is that you have the The "Delete cached copies of roaming profiles" policy is turned on, see "Microsoft installer packages may be reinstalled when you start a packaged program in Windows XP"