Si lo que has hecho es reinstalar el steam te recomiendo que lo desinstales y borres la carpeta y luego lo reinstalas.
La clave que trae tan solo es para activar la cuenta (solo se hace una vez, si ya la activaste en su dia no tienes que volver a hacerlo mas.) y el CD que tengas es donde te vienen los juegos ( cs 1.x , Left 4 Dead, COD etc) segun lo que hayas comprado.
Una vez inicies tu cuenta solo tienes que pinchar en lista del menu principal el juego que quieras y se instalara en la cuenta, a partir de ahi podrás jugar.
Si sólo se puediesen instalar 1 vez el que quisiera formatear el ordenador tendria que comprarse un steam cada x tiempo cosa que no es así xD.
P.D: No creo que te la hayan robado.