I, too, deleted the Windows Fax & Scan shortcut, and when I went to search for it, I, too, could not find it.
Why? Here's my theory...
The SHORTCUT was named "Windows Fax & Scan", but the PROGRAM is called "wfs.exe". The shortcut was deleted, but the program remains, unaltered from it's original 'wfs.exe".
If you do a search for wfs, it shows up right away. Thanks to this thread, I knew what to search for.