В проводнике Windows расширение файла для ссылок (lnk) никогда не отображается, даже если вы отключили Скрыть расширения для файлов известных типов .
Поэтому, если вы хотите удалить ярлык «Ярлык для foobar.exe», вам нужно сделать
File.Delete("Shortcut to foobar.exe.lnk");