I'm not sure why the file is replaced by the original notepad.exe after a reboot. I presume you replaced both "windows\notepad.exe" and "windows\system32\notepad.exe" and not just one of them?
I did some research and couldn't find anything that can explain why the original notepad.exe where restored on your computer, but not on mine. Using Windows XP you have WFP (Windows File Protection), but using Vista or 2008 Server they call it WRP.Parts of this is info from the MS website:
WRP protects files with the following extensions that are installed by Windows Server 2008 or Windows Vista: .dll, .exe, .ocx, and .sys. In addition WRP protects critical files that are installed by Windows Server 2008 or Windows Vista that include a lot more extentions then those listed above.
WRP copies files that are needed to restart Windows in the cache directory located at %Windir%\winsxs\Backup. Critical files that are not needed to restart Windows are not copied to the cache directory. Vista also use ACL (the permissions) to prevent even administrators full access to files installed by Vista.
According to this info and the fact that notepad.exe is not needed to restart windows i would assume it's not copied to the cache directory. I Couldn't find any copies of notepad.exe under "windows\winsxs\backup" on my computer, but you could check on your computer to see if it's there (check the sub directories and include hidden/system files as well). I found some copies of notepad.exe on my computer under some sub directories in the "windows\winsxs" directory (those files where not under the backup directory though), but i didn't do anything with those copies.
If you find some copies under winsxs\backup you might have to delete that file and probably required to change the ownership on those file as well if copies of notepad.exe is found somewhere under the backup directory. I also remember when using XP that i had to delete the file from the dllcache directory, system32 and windows directory. In addition i had to make sure that the windows installation CD where not available to windows to prevent the file from being restored from the installation media. So make sure Vista have no place to find the original notepad.exe.
What I did on my computer is to change the ownership of notepad.exe in the windows and system32 directory. Then I renamed or copied the original notepad.exe to notepadw.exe in both directories before I copied the notepad replacement file into both windows and the system32 directory. I cannot remember if I renamed or copied the original notepad.exe to notepadw.exe. I restarted the computer a lot of times after this operation and never had any issues.
My current notepad.exe (the notepad replacement file) in my windows and system32 directory have the following permissions: SYSTEM, Administrators and Users have read and execute. TrustedInstalled have full access.
I also found this information: forum.soft32.com/windows/Undeletable-folders-ftopict362046.html
So using the info found here it should be easy to create a bat/cmd file that take ownership and replace notepad.exe by running the batchfile instead of doing all of this manually.
If this info is of no help I'm not sure why this happen on your computer since I'm unable to see the same problem on my computer. I tried using a second computer with Vista as well, but had no problems replacing notepad.exe and after a reboot I still found the replacement file under windows and the system32 directory. My windows Vista installation is not preinstalled, but a clean install using a original Windows Vista OEM DVD.Some of the preinstalled windows installation might have some special/strange setup.