Correct. You should be able to enter the original key I believe rather than have a disk, since the disk is generic, or if you have the harddrive with the installation live so it can check it. Then you should be able to do a format if needed and do the clean install.
Or with Vista as you mention, do the actual upgrade over the existing installation, but I understand they need to be like editions, i.e. Home Premium to Home Premium or Professional to Professional, and x86 to x86 or x64 to x64.