If your phone is rooted, try deleting the app's data folder in /data/data.
I don't know why a reboot causes the apps to disappear, but this may allow you to reinstall the app back.