I've said it before, but I think both of you are wrong about the conservative justices; their opinions come from well-thought out schools of constitutional interpretation and Justice Thomas's rejection of substantive due process is hardly comparable to slavery.
I wanted to do a bit more looking into this since I don't think its as clear cut as it at first looks. In fact, current precedent would actually seem to support such a policy. The Chinese Exclusion Cases are still controlling law and say this:
Cases since then have always reinforced the central point that the Court won't second-guess immigration policy; the Courts don't want to create separation of power issues by interfering with something that is absolutely a plenary power of the other branches.
Figuring out how the Court could overturn this is an interesting question. I don't THINK they'd be able to use the Fourteenth Amendment/equal protection for this case. The EP clause reads "nor deny to any person within its jurisdiction the equal protection of the laws." Are potential immigrants within the jurisdiction of the United States? I'm not really sure they are and precedent points to the answer being "no". Similarly, its hard to say the state is depriving someone of due process when they're not even within its jurisdiction, though a big DP fan like Kennedy might look there.
If the court did want to step in, my guess is that they'd have to use the Establishment Clause. Look at the Establishment Clause test from Sch. Dist. of Abington Twp. v. Schempp:
I am absolutely 100% sure that no Justice on the Court right now, if they used this analysis, would say that there was an overriding secular legislative purpose/effect. Courts have shown a willingness in the past to ignore the government's stated reasoning when it's obviously a lie and there's no way they'd be doing a some weak-tea rational basis analysis for this issue anyway. My guess is that if they don't just say "It's immigration, we're leaving it alone" you'd get 8 justices overturning the regulation on that.
Thomas wouldn't, not because of Wolverine's Christianity thing, but because of Thomas's originalist interpretation of the clause. Thomas laid out his opinion pretty clearly in his concurrence in Cutter v. Wilkinson. Looking at the wording of the clause and the debates among the founders, he came to the (probably true) opinion that the clause was ONLY meant to stop the actual establishment (requiring mandatory tithes and attendance) of a religion by Congress and nothing else. I guess he'd vote against an Establishment Clause usage.
You could probably also use a 13th amendment badge of servitude argument or try to apply the arbitrary and capricious standard from the Administrative Procedures Act to DHS's enforcement, but I don't think those are very good ideas.