Here is a short tip on how to detect if a tombstone happened.
Source: Windows Phone Developer FAQ
You mentioned not to use StartupMode to detect a tombstone, how should it be done?
If you just want to detect if a tombstone happened, simply set a flag in your App’s handler to Deactivated event. If the value of the flag has not been reset (in Activated event) , then the app was not terminated.