If one state wanted to refuse to recognize the existence of corporations and LLCs from another state, could they legally/constitutionally? Suppose Maine did not want to recognize New Mexico corporations for some reason. (I picked those states randomly.) Could Maine pass a law making New Mexico corporations and LLCs legally nonexistent in Maine (and removing the corporate veil in cases where Maine courts have jurisdiction)?
"Could Maine pass a law making New Mexico corporations and LLCs legally nonexistent in Maine (and removing the corporate veil in cases where Maine courts have jurisdiction)?"
One might think that the privileges and immunities clause of Article IV, Section 2 of the U.S. Constitution (as opposed to the privileges and immunities clause of the 14th Amendment) might also invalidate this law (e.g., it also prohibits residents of another state from obtaining occupational licenses in a state). But, this is not the case, because the U.S. Supreme Court held in Paul v. Virginia, 75 U.S. 168, 180 (1868), that corporations are not protected by the privileges and immunities clause. See generally, here.
This doesn't mean that Maine couldn't regulate foreign corporations in some manner that doesn't unduly discriminate against out of state corporations.
For example, most states require out of state corporations that do business in that state to pay a small fee and make a simple filing with the Secretary of State of that state authorizing them to do business in that state as a precondition to filing lawsuits or counterclaims seeking relief in their state's courts. But, this is far from a denial of the very existence of the out of state corporation and doesn't, for example, prohibit the out of state corporation from defending itself against suits brought against it in that state's courts. Likewise, it does not prohibit an out of state corporation from owning property or from affording limited liability protections to its owners.
This is supplemental information which aims to support and definitely not contradict ohwilleke's answer.
To do business in most states, a "foreign" (meaning: out of state) corporation must register with the state.
They must also establish a Registered Agent in that state, who must have a street address (not a mailbox) and be staffed normal business hours.
The main purpose of both requirements is to facilitate government actions or lawsuits against the corporation. The state filing is so the state knows who the corporation is (this index is typically searchable by the public, often on the Web). And the Registered Agent is so there is a flesh and blood human for a process server to deliver legal service (notification of actions or lawsuits.)
There is a legal definition for "doing business in a state" which is somewhat more than merely shipping mail-order items there. It varies.
If you are in breach of the registration requirements, that puts you at disadvantage for procedural parts of a lawsuit. For instance, you might hear from a collection agent out of the blue, collecting a judgment on a lawsuit that you partially lost. When you have your legal department look into it, it turns out the plaintiff came into court and said "I was unable to serve defendant because there is no record in the state's database, and, the company's activities in the state are of a level that requires this".
In that case, depending on the complaint and the quality of evidence, the judge may decide to balance "punishing you for not being registered" with "overall fairness", and go ahead and adjudicate the case without you. It's not sports, you don't get a "forfeit" - the judge will rule fairly with the evidence available - your procedural problem is you don't get to answer, present evidence or cross-examine evidence. You could well win. But if you lost... now you're on your back foot, trying to justify why the court should vacate the judgment and let you have your day in court. Anything could happen... that's kind of my point.
This wouldn't pierce the corporate veil, for reasons discussed by ohwilleke.
If the New Mexico corporation does business in Maine, it would be wise for it to obtain foreign qualification – this page assembles links and summaries of the process for all 50 states. However, if the NM corporation doesn't do business in Maine, it's not clear what scenario you have in mind that would affect the NM corporation. Since the NM company is not operating in Maine, it isn't subject to Maine law, and Maine courts would not have jurisdiction.