It sounds like this is just a case of valve/steam not having spent the time or resources chasing after what is (to them) a problem facing a very minor subset of their total user base. Yes, it sucks, but short of a large outcry for providing publishers and such a way to resolve this issue it's unlikely to be resolved. That said, by all means raise a fuss on the steam forums and start calling them - it's possible with enough people pushing it might just get fixed.
Well, actually, I don't think that would work. You see, for them to let you use keys bought elsewhere to activate the game on steam and gain access to all the benefits of having actually purchased it on steam (including downloading it through them, which costs them money)... is a courtesy. They don't have to do it. The problem of someone else having pirated the "remote" key and having beaten the legitimate customer "to the punch" and activating it on steam first is one of those that's tough enough that they'd probably be more likely to just stop doing the cross-activations altogether. More trouble than it's worth. Honestly, if I were in their position that's how I'd see it, if people kept fussing at me about it.
Edit - of course, there is (theoretically) an easy fix to prevent this from being a problem. Steam could provide publishers a way to submit all sold cd keys. If you try to register a key not on the list it doesn't let you, even if it's valid. The publisher would, of course, have to let you know that it will be X amount of time before you can register with steam/impulse/whatever, but that's a fair trade-off for this particular edge case.
We don't actually know which keys have been sold by which other distributors, only those keys purchased directly through our own store. And I'm not actually sure if we have particularly easy access to that data (Chris handles all the store stuff).
Anyway,
the core problem here is that some users are stealing from legitimate customers by activating pirated keys on steam (and on impulse too, I guess, dunno). We don't put any DRM (aside from the super-unaware serial key system; without it you couldn't activate the game on steam at all) in our game because we don't want to inconvenience legitimate customers. However in this case some pirates have declined to show the same courtesy. Perhaps (hopefully) they did not realize how the system works and that they were directly harming other users.
Thankfully, that theft only applies to access to the benefits of having bought the game through steam when you actually bought it somewhere else. We do try to make clear that we can't 100% guarantee that access anyway. The only way to do that is to buy directly from steam.
As for us issuing replacement keys to folks experiencing this, there are a number of logistical and other issues with that solution. It's up to Chris in any event.
