I have been seing this behavior as well for quite a while, but none of the suggestions that I see here, and there are many, does the trick. I have to reboot to make it work again. So, that means that Notepad _is_ installed, that it is _not_ a full cache (emptying the cache alone does not help) and I also don't have notepad.exe on my desktop
Any other ideas?