So, are people who on Steam who want a Physical CE just out of luck?

[Kiyaki]

If I may make another suggestion, why not give SE the idea to add a Steam code to the physical collector's edition? Best of both worlds then.

I don't think that would be a viable solution, as it would mean that buying a Collector's Edition nets you two digital CE keys for one, and nothing would really be stopping you from using the one you need and giving away/selling the other one.
That could result in some serious losses on Square's part. The ideal solution is just for Square to come out and either tell people who will be purchasing on Steam there is no viable way for them to buy a physical CE, or acknowledge the flub and pledge to offer Steam keys to people who buy the Physical CE who would need one, though you could argue in doing the latter you'd run into the same problem unless there was a way to void the physical CE's normal key. I guess it boils down to how much they care about customer satisfaction over potential lost revenue.

[worldofneil]

According to my friend who also purchased via Steam and had already pre-ordered the physical copy, that disclaimer was not there when pre-orders first opened up.

Playing devil's advocate, but has your friend actually got proof of that otherwise it'd just be their word against what it says now. Don't get me wrong I think the Steam/Non-Steam policy sucks, but I can't see them offering refunds after they've shipped orders because the codes won't work etc when it (currently) says about that on the ordering page.

[Kiyaki]

Playing devil's advocate, but has your friend actually got proof of that otherwise it'd just be their word against what it says now.

Haha, I actually worded that incorrectly. When I said he had purchased via Steam, I was referring to the fact that he purchased ARR via Steam, not Heavensward. Heavensward is not even listed in Steam's system as of now and is not available for purchase. Still, this issue isn't with Steam or Valve from what I've seen.
I hadn't been to the Square Store before today, which is when I pointed out the disclaimer to him and he said that it was not there when he put his preorder up. I trust his word because I know him personally and know he isn't one to buy blindly without research, but I can't confirm or deny it factually since I did not visit the pre-order page in Square's store when it first became available.
As of now, he put in a ticket to customer support and is trying to find out pretty much the same thing I am.

[Saccharin]

Blame valve.