> The next time I looked though the installed apps I saw some Vodafone Services app that I didn't install. It couldn't be removed either
Are you sure that's an actual Android App and not just the SIM Application Toolkit[0]? On iOS these show up under the Carrier menu in Settings but on Android it shows them as if they were an app, even though it's something running on your SIM card (they are backwards compatible and show up way back on old feature phones).
That's a very good point! I removed the SIM and the app was gone again. So I guess you're right, it may be installed on the SIM and not actually the device.
Are you sure that's an actual Android App and not just the SIM Application Toolkit[0]? On iOS these show up under the Carrier menu in Settings but on Android it shows them as if they were an app, even though it's something running on your SIM card (they are backwards compatible and show up way back on old feature phones).
https://en.wikipedia.org/wiki/SIM_Application_Toolkit