Thanks to some great comments and a specific one from James I have now replaced notepade.exe with the vastly superior notepad2.exe and prevented Windows File Protection from replacing the new notepad.

Here are the steps (warning, process with care, no warranties etc):

Method 1

1) Rename Notepad2.exe to Notepad.exe
2) go to %windir%\system32
3) Rename Notepad.exe to NotepadX.exe
4) go to %windir%\system32\Restore
5) Turn off hide invisible files in Tools->Folder Options->View
6) Select filelist.xml and right click->Properties and uncheck Read-only
7) Edit the file
8) Add:

<REC>%windir%\notepad.exe</REC>

to:

<Exclude>
    <REC>%windir%\system.ini</REC>
    <REC>%windir%\tasks\desktop.ini</REC>
    <REC>%windir%\win.ini</REC>
    <REC>*:\AUTOEXEC.BAT</REC>
    <REC>*:\CONFIG.MSI</REC>
    <REC>*:\CONFIG.SYS</REC>
</Exclude>

9) copy the newly renamed notepad2.exe (now named notepad.exe) to %windir%\system32

note: it turns out that for some folks, this doesn't work. It did not work for me on my tablet pc. Thanks to Shakeel Mahate here is method #2.

Method 2

1. Tools->Folder Options->View uncheck Hide protected operating system files. 
2. rename Notepad2.exe notepad.exe 
3. copy notepad.exe %windir%/system32\dllcache 
4. copy notepad.exe %windir%/system32 
5. A dialog will popup hit cancel 
6. Recheck Hide protected operating system files in the Folder Options dialog box

The dllcache contains copies of the windows protected files. The dllcache isnt itself protected.