Let's start by going through what you have already tried:
The Disk Cleanup Wizard can increase the amount of free space on the
hard drive, but a computer performs its work in RAM, not the hard drive,
so freeing up space does not affect a computer's performance. (The only
exception is where the hard drive is almost completely filled - but you
would know if that was the case.)
With the speed of today's hardware it's not likely that defragging will
increase performance enough to be noticeable. These days, defragging is
more about preventing program errors. Nonetheless, defrag is a valid
approach to slow performance.
"Removing all unwanted programs" -- See my note on the Disk Cleanup
Wizatd above.
Desktop shortcuts have nothing to do with a computer's performance.
So-called registry cleaners (like RegCure) have no proven value and can
easily cause irreparable damage to a computer.
History and cookies have no effect on the speed of a computer.
On the other hand, viruses and other malware -- few infections are viral
these days -- can certainly slow a computer.
Slow performance is easy to understand: It means that your CPU and/or
RAM are not able to process the work you giving them quickly enough. The
solutions are:
1- Reduce the workload on your processor and RAM: This means closing
memory- and processor-intensive applications until your computer's
performance becomes acceptable, or
2- Upgrade your RAM and/or CPU. (Financially it makes more sense to
increase the amount of RAM.)
Two more things to keep in mind: Malware infections are often very
memory- and processor-intensive. Also, if you have compromised your
system with incorrect settings (for example, by fiddling with virtual
memory) and using so-called registry cleaners, you can cause performance
to decrease.
Make sure that your anti-malware software is running, then download the
latest signatures and run a full scan.
If you don't have comprehensive anti-malware software, that's like
driving a car without seats belts or air bags. Either way, you're
eventually going to get hammered. Install comprehensive anti-malware
software and learn how to use its features. A 'comprehensive' solution
scans for all types of malicious software in the background, on demand
and on schedule.
For now try scanning your system with /several/ of the better online
scanners, such as:
Kaspersky Antivirus (
http://www.kaspersky.com/virusscanner)
Panda ActiveScan (
http://www.pandasoftware.com/activescan)
Download HijackThis from
www.trendsecure.com. Run it, save a log, and
post the log at one of the many sites that support HJT, such as
spywarewarrior.com, bleepingcomputer.com, and temerc.com -- but not
here. Within a day, sometimes within an hour, you'll have one-on-one
step-by-step advice from a security expert on cleaning up any
infestations—or you'll have a clean bill of health from the volunteer
expert.
Even the best detection and removal software can't fix every malware
infection. If none of the above remove the infection, you may want to
show the computer to a professional.