Legal or not legal isn't determined by the licence key anyway. You can buy it for real, then crack it and you still have a legal copy.

Actually, no... it's telling you that it thinks it's not a legal copy. The company doesn't actually know. It's not like they sit down and write out by hand every key that is created. Those keys are generated by some algorithm. The company can identify if an algorithm was compromised (either the generation method identified or a significant portion of keys from said algorithm being used without them having been generated by the company), or they surmise that a chunk of codes, that had been previously generated for distribution, were nabbed when a number of them start to get activated without the company seeing a corresponding increase in sales. They more than likely do not have an exact list of which codes were stolen, just an assumption.

Here's an example for ya... Company gives Legit LTD a set of codes to sell. Unfortunately, the thieves seal hack into Legit LTD's systems and are able to copy a chunk of those codes. Legit LTD does not realize the breach for a day, or a week, and sells those codes to customers. At the same time, the thieves setup a seeming legit web store and started selling their ill gotten codes on that site. Two different customers are looking for Company's software. One buys a code from Legit LTD. The other buys from thieves seemingly legit store. Just so happens that both stores sold the same code. Now two people have a copy of the same code. Both customers, in this case, believed they were buying a legit code. Both believe their code is valid. Before either can activate those codes, however, Legit LTD realizes they've been hacked and tell Company. Company, not knowing exactly which codes were stolen, decides to invalidate the batch... but there are legit customers in the wild that have codes from that batch and there's no way for Company to tell who bought from who. BOTH customers, at this point, go to activate their code and both are told they're running a pirated code. Neither of them really pirated, however. The thief did, but the thief isn't the run using the code.

As such, no... Company and Legit LTD would find it very difficult, if not impossible, to determine who bought legitimately. Most companies, when this happens, would say, fuck'em and let both customers suffer. This company chooses to tell them they're running suspected pirated codes (though, they don't know for sure), and, regardless, neither customer would be pirating because both believe they purchased legit codes all above board.

Welcome to software, my friend. :D