If you are of interest to the US government or any ally, assume your phone comes back from inspection with a compromised bootloader that will continuously re-infect your phone after you wipe/reinstall.
Wipe it, let them inspect it, sell it, and buy a new one.
For non-citizens, there's not really any law against them installing malware on your phone which could persist through a factory reset. Though I've not heard of such malware for flagship phones.
I have heard of malware like this, and engineers that found it at Google were instructed by higher ups to ignore it and never talk about it without explanation.
Good luck getting anyone close to this to go on the record about it though given such things normally come with corporate or government gag orders.
There are hundreds of privileged vendor binary blobs on most flagship devices not even Google gets source code to though so supply chain attacks should be assumed.
I think this is broadly not true.
Sure, the NSA can probably pull this off. Thing is, the NSA probably does not need to do this at immigration.
I seriously doubt that this is a realistic problem if your threat model is anything less than "The NSA is very interested in me". In that case I don't see how you could trust any phone, regardless of it having been in the hands of border officials or not.
isn't the right move here: wipe your phone, travel to destination, then restore from cloud backup? in the middle, you can let them inspect your wiped phone.