if the game was bought on ebay you most likely bought it off some guy who already registered it with steam so you cant use it, and if you really cant use it the only things you can do is buy a new one, or as you said, send 10 dollars + your copy of half life to valve (should stand somewhere on
www.steampowered.com) and you will get a new copy or cdkey or something.
Thats why they always say you should never buy games off internet auction houses such as Ebay. And yes you can also just buy a cd-key trough steam, once you buy the cdkey trough steam, you get the cdkey, go to "Browse games" and then "Register a product with a cdkey" (or something similair to that)