Just offhand, and this is just a probable but not an absolute, but it sounds like from all the things you have done to address the problem that this is a matter where some exploit has compromised the Android OS on your phone.
To fix something like this, you'll need to re-flash the stock ROM. Flashing a ROM is basically similar to a 'restore from image' process on a computer, where the original operating system replaces the problematic operating system. Stock ROMs are very model specific, so what is the exact model I.D. of your S7 Edge, which version of Android is it running, and who is your cellular carrier?
Regarding some of the things you already tried
-- Your phone's internal storage is divided into several partitions. Most are protected system partitions, and there's one that's the user data partition. The data partition is where all your data and apps you install are stored. As for the operating system partitions, unless you root your phone you only have very limited access to anything stored on them.
That's an important point because an anti-virus/anti-malware app that you install yourself is installed without system privileges so while it has complete access to that entire data partition, it can do very little to those system partitions. Another thing to keep in mind is there is no AV or malware cleanup utility in existence that can detect everything, and even more importantly never assume just because some app found and claimed to fix a problem that means there aren't others still there.
-- Also, a Factory Reset will only wipe that data partition clean, it does not have any affect on the system partitions. If the exploit was located in the data partition than it will get deleted but an OS that was infected before a Factory Reset will remain infected afterwards.
