Cannot Run Regedit.exe

I have a massive infection. I came to my wife's family in the Philippines and the computer is massively infected.

Symptoms:
Cannot run regedit.exe - I tried to run this from command.com but it returns "The system cannot locate the file C:\WINDOWS\regedit.exe."
Run command missing from Start Menu - I'm pretty sure this is a symptom as I'm also barred from modifying the settings for Start Menu.
Self-replicating executables - One copy of each is found on my desktop, games.exe, mp3.exe and videos.exe. Each of these use a folder icon to disguise themselves. Immediately when deleted, these files re-appear!
Internet Explorer Title Bar Hijacked - The Internet Explorer title bar reads the usual title for the webpage, then appends "Bisdak for Life" which roughly translated means Visayan for Life, or in other words, !@#$ the Tagalogs of Manila!
CMOS settings lost - I replaced the CMOS battery already, and the problem persists. If the computer is turned off for a minute or two, the CMOS settings are lost including date and time etc.
Task Manager Disabled. - Upon pressing Ctrl-Alt-Delete or trying to access the taskmanger through command.com, I'm getting the following message: "Task Manager has been disabled by your Administrator." I am the admin of course, and I did check the settings using gpedit.msc, everything is fine there.
Memory spikes - I can see the memory spikes in the performance log, and they cause a breaks in computer usability. For example, while typing, the text may paus for about 1 second before displaying. Intervals are about 2-5 seconds.

System Specs:
Microsoft Windows XP Professional Version 2002 Service Pack 2
Intel® Celeron® CPU 420 @ 1.60GHz 1.60 GHz, 504 MB of RAM

I'm not sure which of those symptoms may or may not be related to a single infection or how many infections I may have. I haven't tried anything major yet except to Google Bisdak for Life, but only got about 2 hits on that. You guys have been very helpful in the past and I hope you will be able to help me again. Thanx.

Edited by hamluis, 12 February 2011 - 08:04 AM.
Moved to AII.

With the information you have provided I believe you will need help from the malware removal team. I would like you to start a new thread and post a DDS log HERE and include a link to this thread. Please make sure that you read the information about getting started before you start your thread.

It would be helpful if you post a note here once you have completed the steps in the guide and have started your topic in malware removal. Good luck and be patient. Help is on the way!