A phone I had to restore had malware apps ("MonkeyTest" / "TimeService") installed which would flash in apps, download more malware, keep installing each other and so on. These apps persisted through factory resets.
Surprisingly the phone was rooted already so I flashed a CyanogenMod ROM, after flashing ClockworkMod Recovery and wiping all data I could select.
It's annoying that there are apps almost every week that need to be updated. For example stuff like Amazon and the worst is the NFL app. Anyway I wanted to uninstall some of these apps through application manager but it seems that apps that came with the phone can't be uninstalled. There is no uninstall option. The only time there is a uninstall option is when it's a app I installed myself.