Half-Life CD-Key Already In Use

I bought Half-Life 2 a while back, and much to my annoyance I discovered Steam. I know it’s great in theory, but in practice it’s a pain in the ass. Especially when you need an update and you only have 56k dial-up. After completing the game, which was amazing apart from the end which I found too easy, I decided to install my original copy of Half-Life and the Opposing Force expansion pack. When I tried to register this on Steam I got a message saying that it was already registered. I know I never registered it! What do I do? Here’s the answer.
Thanks to someone using a key generator my CD-Key is now registered to someone else and I have to pay Valve a $10.00 handling fee to have it reset and assigned to my account. Alternatively, I could just go and buy a new copy. Lovely!