Understood that files you want to keep have been saved elsewhere?

If you want to start with a fresh, clean, hard drive with no data anywhere on it, use Dban here: http://www.dban.org/ This is a hard drive wiping utility that overwrites all data on the hard drive. Once the wipe is done, you can restore the hard drive to like new condition by having Dban write zeros to the drive.

This will dispense of the second Vista install as well.

OR,

When you begin installing Vista, there will be an option to format a part of the drive, or all of it, as NTFS. Formatting should reset the file system, but rarely, but does happen sometimes, stubborn malware survives a format.

Sounds as if you may have had a hidden rootkit on your system (Google Redirect Virus), so starting fresh with a clean disk is likely the best option.

Another option to consider (less time involved, as Dban does take a long time to run) is to get a new hard drive, and put that one in after taking the old one out. If you are thinking of throwing the old one out, don't. Wipe it with Dban first, then toss it.