When I inserted the Windows 7 CD and booted from it, I selected the Custom box and formatted/deleted the partitions. Is that not the option for a clean install? If not, what is the option for the clean install?
I do not know the keys.
Yes, if you deleted the widows partition and recreated it, then it's a clean install and no random registry keys will exist. If the key is back, you reintroduced it somehow.