Judging from that image, I would say that message is generated from spyware/adware. I would say that Microsoft (or any REAL company for that matter) would not use grammar such as "Your Windows is corrupted with spyware virus", so that's a pretty good indicator.
Have you tried running the scans in Safe mode, as suggested by dee_sel above?