Remote notification on Android, when the game is not run in background.

I have complemented prime31's Google Cloud Messaging plugin for remote notification. It work's fine when my game is run before and in background, but not when the devices is restarted so my game not in background.

I've been told that it is not possible for Unity since it's not a Java native code etc.

Then I think it totally lost the meaning of remote notification, which is to send notification to users who didn't play the game for days and want them to come back...

There's also plugin App42 API and number of 3-rd party companies such as GameDonia, will that do the trick?