Do your words ([italics]having done a full hard drive delete[/italics]) mean that the last install was Vista only or was it XP followed by a Vista upgrade?

If it was Vista only:
1. Run the System File Checker (SFC) from an elevated Command Prompt, i.e. click the Windows Orb (Start) > All Programs > Accessories and right-click Command Prompt, then ‘Run as Administrator’. Type sfc /scannow (note the space) and press Enter. This may take some time and you may have to put the Vista DVD in the drive.
2. Run a Vista startup repair. This can repair a lot of problems http://www.vistax64.com/tutorials/91467-startup-repair.html

If it was XP followed by an upgrade:
3. Was the XP version, SP2?
4. Did you run the Vista Upgrade Advisor before installing Vista?

Finally, I wouldn’t rule out an infection!