Is it possible to detect Android app uninstall?

Unfortunately the ACTION_PACKAGE_REMOVED intent will be sent out to all receivers except for your own. This is confirmed here.

Some questions for your C2DM plan, since I'm not very familiar with it. If the user just leaves their device off for a long period of time, will that trigger the error condition you use? How does C2DM actually report an "unreachable" device? Is that a condition that only occurs when it attempts to send the push notification and fails or is it when it somehow determines it reaches the device but fails to be handled properly? Obviously in the second scenario your plan would work, but I can see some "false positives" occurring otherwise.

Older SO question for reference: android not receiving Intent ACTION_PACKAGE_REMOVED in the removed package