Mr. McMaken, my reading is that the Constitution, while it authorizes Congress "[t]o establish a uniform rule of naturalization," does not enable it to regulate immigration per se. Unless it is treated as a full-blown invasion, the federal government must leave immigration to the states. (And I fear what it would do if it were legally decided that we were being "invaded.")
I strongly agree with what you say about the distinction between legal and illegal immigration. No matter what a libertarian thinks of immigration, I believe he should not rely on the state's designation of someone as an "illegal" person as some sort of guideline.
I wrote about this distinction in an LRC article:
From a purely anti-state perspective, the whole notion of illegal immigration is weighed down by absurdity. This is not to say that mass immigration is never a threat to the property rights and cultural values of those living within a geographical area. Immigrants who swarm across the borders only to go onto welfare are consuming more than their fair share of the public loot. Immigrants who trample on the private property of Americans living along the border are guilty of trespassing. Many illegal aliens come to America and remain criminals in the true sense. With this in mind, we can probably argue for a distinction between libertarian immigration and non-libertarian immigration.But the concept of illegal immigration – whereby a monopolistic coercive entity draws some line in the sand and dictates who can cross it, fining and jailing and shooting those that defy its rule – is ridiculous.