I certainly would not begin with reformat reinstall. I would suggest first that you follow the instructions for downloading, updating and running MBA-M. Please have it remove everything found. Post back with the log.
Please download Malwarebytes' Anti-Malware (MBA-M) to your Desktop.

  • DoubleClick mbam-setup.exe and follow the prompts to install MBA-M.
  • Be sure a checkmark is placed next to Update Malwarebytes' Anti-Malware and Launch Malwarebytes' Anti-Malware, then click Finish.
  • If an update is found, it will download and install the latest version.
  • Once the program has loaded, select Perform full scan, then click Scan.
  • When the scan is complete, click OK, then Show Results to view the results.
  • Be sure that everything is checked, and click Remove Selected.
  • When MBA-M finishes, Notepad will open with the log. Please save it where you can find it easily. The log can also be opened by going to Start > All Programs > Malwarebytes' Anti-Malware > Logs > log-date.txt.

What online scan did you run?

If the computer DOES definitely show as clean then do the following:
try downloading the standalone install for the Service Pack and save it to the desktop. Then disconnect from the internet, turn off AV program and firewall and try installing that way.

You can get the Standalone version from HERE