"Once they're on US soil (or, probably, in US airspace, not sure how that law works), then we can start talking constitutional protections. Until then, they're not relevant."
This isn't entirely correct. The original purpose of the US constitution was and arguably still is to constrain US government authority. Those constraints apply to the government whether it is operating within the US, on the other side of the world, or in the fictional no-man's land of JFK's arrivals lounge.
A really good example of this is the 2008 ruling in Boumediene v. Bush[1], which determined that habeus corpus applies even to foreign, non-citizen "combatants" held overseas who have never even so much as seen the US.
It's also the reason why Trump's repeated attempts to ban brown people from flying to the US have been shot down. While the US government may regulate immigration, it may not infringe on the immigrant's right to religious freedom by setting out a preference for one religion over another. Not because their religious freedom is inherently protected (e.g. as under European Law) but because the US government is banned from doing so by its own constitution.
So the question comes down to not whether the traveler is protected against these searches, but rather whether such searches are constitutionally permitted in general. Unfortunately the overwhelming majority of case law points to this kind of thing being well within the government's purview (primarily by distinguishing between "person" and "citizen"), as long as it is not being abused to discriminate. That could well be up for challenge, but given you wouldn't be allowed into the US to challenge it in the first place you'd struggle to find cause.
[1]https://www.law.cornell.edu/supct/html/06-1195.ZS.html
Biting the hand that feeds IT
