All the HP's I used never had me enter the key. If you tried to install Vista and put in the product key then it is indeed non-genuine.

Remember I'm taking your word here about that product key and your story. Now install again but with the restore media and not a Vista DVD.