I know that launchers normally detect when the package was installed/uninstalled. That's how they refresh the list of app icons. And launcher is just a regular app with no special permissions. I think some kind of an intent is broadcasted when the list of apps is changed.

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