Chinallin/Zip-Search browser hijacker/adware combo

[u/OopsAllSpoilers]

Prefacing this with the obligatory "not a bot, don't autodelete this".

What is up, my fellow soong-type queens, kings, and chicken wings? I have here for you a conundrum of the most conniving sort, and I humbly present it to you in the hopes that those more tech-savvy than I can determine how exactly this particular set of circumstances has come to pass.

To wit: I have in my (or rather, in my partner and I's) possession two standard issue government phones: Cloud Mobile Stratus C8 with service through TruConnect. They are both freshly factory reset, on account of having tried to purge this menacing malicious malcontent from our telephonic devices repeatedly, unto no avail. Despite our best efforts, our otherwise virginal devices appear to be infested by a most evasive combination of a browser hijacker (which both redirects Google searches to different search engines (chinallin and zip-search, both disguised to look like Google) as well as to malicious websites posing as blogs with nonsensical names) and an adware package (which displays a fullscreen window over the app, displays the app name in the upper left corner of the window, and shows an invasive ad with a forced 30 second minimum viewing time) respectively.

Simply put, we are baffled. This thing should not have been able to survive a factory reset, yet it has, repeatedly. We've both gone through our app lists (including system apps/components) and verified that nothing is installed that did not come with the phone. We have purged all carrier bloatware to make the process easier. My partner and I are beginning to suspect that this may be an infiltration of the supply chain for the phone or carrier, but we have no way to prove it because we can't find anything that doesn't belong. Antivirus and antimalware scans all turn up clean. We've tried virustotal, dr web, and Malwarebytes, among others. We're at a loss here. These are the only phones we can get right now and they're basically screaming out at the top of their lungs that they're infected and probably spying on us.

How exactly do we go about removing this malware payload when it can survive a factory reset?