In Tennessee v. FCC, [1] the FCC, under the authority of §706 of the Telecommunications Act of 1996, attempted to preempt state laws that prohibit municipalities from building their own broadband networks under certain circumstances (these laws were obviously lobbied and passed by ISPs in the state legislatures). This was struck down by courts because, although the supremacy clause means that federal law supplants state law, the federal law at hand was so far removed from what the FCC was doing in this particular case, that the FCC was essentially creating "directives" which overruled state law in pursuit of a vague goal that was defined in federal law. In essence, federal administrators/bureaucrats had the power to overrule state law. Although the ISPs "won" in that decision, it cuts both ways -- which means that any attempt by the FCC to preempt net neutrality regulations under §706 is likely to fail as well.

Sorry if my take is a little confusing, here is some more coverage: [2], [3].

[1] http://www.opn.ca6.uscourts.gov/opinions.pdf/16a0189p-06.pdf

[2] https://www.forbes.com/sites/danielfisher/2016/08/10/fcc-los...

[3] https://arstechnica.com/tech-policy/2016/08/in-blow-to-muni-...

Problem is: if New Mexico passes a Net Neutrality law but all of the Netflix data centers are in Arizona it's suddenly going to be "interstate commerce"

Yes, and congress could pass a law banning net neutrality. But under current law, the FCC is not able to issue a directive doing the same thing.

A law banning NN will never get passed due to gridlock (thankfully), so barring some huge change in public opinion I don't see states being prohibited from enforcing NN.

Something being interstate commerce does not prevent states from legislating on it. Under that logic, states couldn't regulate the sale of anything produced in another state, which is obviously untrue.

no it just means that the federal government has constitutional power to over rule it if they feel like it, no need to argue on the basis of any existing case law.

States have room to pass whatever regulation they want by default. It only becomes a problem when it conflicts with federal law, in which case federal law always takes precedence.