Icons vanish if computer not restarted

When our application is installed, it sometimes requires a reboot. This reboot is optional, and is not usually required, except on the first install of the program. However, when the software is installed silently on startup, the application starts after the install without knowing it needs to reboot. When the application starts after the install, all of the icons just installed (including the startup icon) disappear from the machine. It is almost as if the application is being uninstalled? Has anyone seen this?

Thanks

amaddux