This is largely due to a limitation of Android itself. If your app wants to do any sort of background task that's not tied to Google Cloud Messaging, it needs to setup those background tasks. When your phone reboots, those tasks are cleared. Many apps use the "run at startup" permission to receive a notification from the system when startup has completed. It doesn't actually mean the app is running in the background.