Android apps can't have that permission, only the Market gets that permission.
No offense, but you're spreading some pretty false FUD. Unrevoked uses multiple exploits and requires a lot of user interaction and a computer to initiate the process.
Further that last link basically describes how Play remote installs applications and is all under the assumption that someone has somehow MITM the SSL connection, something I'm presuming is not at all easily done. (Further it's going on two years old, I wouldn't be shocked if Google is now signing their INSTALL_ASSET messages, Play has changed a LOT in the last two years).
Apps are sandboxed overall similarly in iOS, WinRT, Android, WP7. Uninstalling them, uninstalls them. It even removes all data attached assuming the dev doesn't manually put data on the SD card instead of using the API to store data on the SD card.