I "inherited" a computer that had a "cracked" version of Vista on it. I have a legitimate version of Vista and wanted to install it.
I installed it and had it format the hard drive. During the installation it never asked for the product code and installed using the cracked product code, which I verified after it installed because there was a product code already there. I believe the code somehow got hard coded into the BIOS.
I have tried to flash the BIOS with the rom from the ASUS website and reinstalling, but no luck. Still keeps installing with the cracked product code. I put in a new hard drive and reinstalled again. No luck.
You don't have to worry about the BIOS, an OS install can't affect it.
Did you format the drive from within the Windows install/setup program? If so then what's probably happened is that the setup program read the old key from the disk before formatting and then applied it to the new system - I've seen this sort of thing happen with XP installs.
Here's what I'd do: Boot into the setup program, delete all of the partitions, then shut down before it can copy any files onto the disk. Then start the setup over again - now that the disk is blank the install program will be forced to install from scratch with no leftovers from the old system.