My OEM HTC keyboard (TouchPal) straight up turned into malware. It was banned from the Play Store... but was unremovable without adb.

There was never a notification either, I just saw it on a news site.