There are now a few infections that will not clear with a factory reset. Since these can do what you noted, there is nothing I can do to help you fix it until Google and Samsung issue a patch to stop such from happening and also, fix factory reset to really reset.

No, I did not tell you it is xHelper. I'm only using it as an example of something awful that you can't deal with.