I always start with ghostboy's bottom link, ad-aware SE personal (actually I use the pro version and uninstall it if it's not my computer, but the malware definitions are the same). Also update and scan your computer with your antivirus software. This eliminates the possibility that your extra resources are being used up by viruses or spyware/adware. I'm a big fan of spybot s & d too, running 2 anti-malware programs is ok, but never run two antivirus programs at the same time as they can make your machine get fritzy. The most common cause is always malware though, those pests are everywhere.
I'm guessing the pop up that says your virtual memory is low is because windows is increasing the size of your paging file? If that is the case then you are already set to system managed size, and eventually the problem will correct itself, unless the problem is you are getting more and more malware using more and more page file for ram. The only way to solve that is to get rid of the malware or virus or manually set the size of your page file, and who wants malware anyway, eh?
Personally I'd stay away from the registry cleaners until you run ad-aware, spybot search and destroy, and update and run your antivirus. Then if you have errors run the cleaners. And run each program once, reboot, run them all again! If you don't have antivirus,
avg free is my favorite, I'm sure others can throw out some options as well.
You could also be due to defragment your hard drive. Windows has one under Start ->All programs --> Accessories --> System tools --> Disk defragmenter. If you're like me and are always adding and removing large files and programs, a program like diskeeper is well worth the money, it has been shown to greatly improve system performance by improving drive seek time.
Adding more RAM is often a very good move. They like to sell them with barely enough to run windows, then stiff you by overcharging for a little stick. Do you know how much your machine has? If not you can check by going to the start menu, right clicking "my computer" and going to "properties". Usually it's down towards the bottom right somewhere.
Hopefully it's not hardware failure. Always (always always always) keep your files backed up, especially your pictures. Burn CDs, get some thumb drives, doesn't matter, hard drives don't last forever. I have to make that phone call a few times a week, rarely do I hear they've backed up their data.
Gah! Just realized this post was from last weekend... oh well, better late than never.