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.

https://www.google.com/search?q=xHelper+%E2%80%93+the+Android+malware+that+won%E2%80%99t+die.

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.