Is there a way to get a system notification when an app has been uninstalled?

I would like to maintain a table of all clients' info currently using my app. However, that seems impossible if there is no way to detect this event.

The first solution I can think of is to have an always running service in the background listening for android.intent.action.PACKAGE_REMOVED. But then would that service be killed once the uninstallation process has ended, or would it be stopped just before the process has kicked off? Also even if this is a solution it's has the potential to put off a lot of people when they realise that part of the app is running in the background.

Any suggestions? Thanks!