From what I understand once an app is removed Android fires a ACTION_PACKAGE_REMOVED intent which can be picked up by other Apps.