it happens with a lot of those types of games. starcraft is similar, in that you can use any correctly hashed key, but once you try to play online, the server requests the key, and if it does not have a record of such a key (legal copy, the key already registered with the server, from being placed on the box) it responds with 'Invalid CD Key', which indicates:
a) you are not the original owner of the game, because someone has already registered it, then decided they hated online play, then resold it; or
b) you bought a program online that hashes a key together, that the cs1.6 installer can use, but cannot use online, since the servers have never seen such a key.
to remedy either of these two situations, you need to buy the game, from a retail outlet or online retail site, not an auction style website, in order to be the original owner.