There's an awful lot of malware out there disguised as registry cleaners, so my policy is to avoid them altogether.
Would bringing the RAM up to 512MB help? Sure. But it IS possible that the utility you downloaded is partly responsible for this problem. I could talk you through undoing it's changes, but the time it would take for such a call would be better spent reloading Windows.
When a program needs more RAM than the 128MB that's installed, Windows will grab a piece of hard drive space and treat it like RAM. Programs don't know the difference between real RAM and Windows "virtual memory", but you might because reading/writing to a hard disc is super slow by comparison.
"Your system is low on virtual memory" means that both RAM and virtual memory are exausted. But virtual memory can be adjusted, and it's pretty easy to do. The shorthand version of the steps are: Control Panel, System, Advanced, Performance, Visual Effects, Adjust for best performance, Advanced, Programs (both radio buttons), Virtual memory, System managed size, Set, OK and reboot.
It's not nearly as confusing as it sounds, but I'll baby step through it below.
1. Go to the Control Panel and double-click on the System icon. This brings up the System Properties window.
2. Click on the Advanced tab, then the Settings button associated with Performance (the topmost of the three shown). This brings up the Performance Options window with Visual Effects as the active tab.
3. Choose "Adjust for best performance", then select the Advanced tab.
4. Choose "Programs" for both Processor scheduling and Memory usage. Next click the Change button in the Virtual memory box. This will bring up the Virtual Memory window.
5. Assure that your primary drive is highlighted in the Drive box and select "System managed size" just below (it may already be selected). Hit the Set button, then OK as required to close 'er up.
6. Reboot.
