This happened to me . My solution was to place a copy of notepad.exe in my C:\windows\system32 folder. I also made it read only to try and prevent it from being deleted again. It seems to have worked.
Windows XP Home, When cwshredder rendered the notepad shortcut in accessories unusable I was able to just replace it with a copy from the DLLCACHE file and it works fine. However I no longer have notepad listed in the OPEN WITH window, anyone know of a way to get it back in there.

Chowhound
Comic Vine
GameFAQs
GameSpot
Giant Bomb
TechRepublic