Heyyo,
Ok, after uninstalling HL, it doesn't delete the registries. So..
Start > Run > regedit
now search for anything half-life, and preferrably export (for backup purposes, always safe, and it's what? 1-10kb?) and then delete.
Now you should be able to reinstall the game. I say, don't just use 2 copies, it's obvious that I'd fail. Each one of you guys just go buy HL1. It's like $15 CAD, that's nothing. USD I bet it's cheaper, euro even more. It's a classic, it's a good one, it's worth it.
After that, you shouldn't get cd key in use problems.