I still think that it's a virus or some kind of spyware. The regedit and taskmgr programs themselves are fine - you rename the file, and they start.

Try this: rename regedit into something else. Now rename notepad to regedit, and try and start it. If it doesn't start, then there's some virus on your computer that's deliberately looking for regedit.exe and is killing it. Something that the scans missed.

And if you have time, see if you can run regedit and taskmgr in Safe Mode.