報告が大変遅くなりました。申し訳ありません。

解決に至りましたので、報告いたします。
問題のあったアプリケーションですが、インストーラーが  InstallShield Limited Edition で作成されたもので、セットアップした際に、自動的にデスクトップにショートカットを作成するように設定されておりましたが、このショートカットがアドバタイズショートカットになっていたことが原因でした。
セットアップ時に普通のショートカットを作成するよう変更したことで解決に至りました。

回答ありがとうございます。

＞ 葉月 様
　ショートカットのリンク先の編集は私も思いつきましたが、
　おっしゃられる通り根本の解決にはならないためこちらの方法は諦めました。


＞ 魔界の仮面弁士 様
　アプリケーションをインストールしている ＰＣ では ＯｎｅＤｒｉｖｅ は使用しておりませんが、
　その他については社内のＰＣについて詳しい者に確認を取ってみます。
　確認にしばらくお時間をください。

もしかして葉月さん、解決チェックを付けましたか?


> デスクトップのショートカットからアプリケーションが起動できなくなるケースがあり、原因がわからなく困っています。

AD (Active Directory) は使われていますか?
企業で使われている PC だと、管理者がショートカットを配置することもあります。
https://qiita.com/t-morisoba/items/8c3411afc7f4b29a2e2f

また、複数の PC で同じ環境を構築できるよう、
移動ユーザープロファイル や フォルダーリダイレクト によって、
ネットワーク上のディスクにファイルが保持されるケースもあります。
https://milestone-of-se.nesuke.com/sv-advanced/activedirectory/roaming-user-profile-and-folder-redirect/



AD では無いとしたら…その PC を複数の異なるユーザーアカウントでログインすることはありますか?

デスクトップ (仮想フォルダー) は、共有のデスクトップと個人のデスクトップという
複数のディレクトリ(物理フォルダー) で構成されています。

C:\Users\(UserName)\Desktop
C:\Users\Public\Desktop

そのため、共有デスクトップのショートカットが書きかえられた場合、
他のユーザーのショートカットも書き換わることになります。今回は違うと思いますが。


それ以外で思い当たる物としては、クラウドストレージ。

最近の環境では、既定で OneDrive への同期バックアップが有効になっているため、
他の PC のデスクトップにあったファイルが、別の PC 上に現れる事があります。
これが原因だったりはしないでしょうか?

C:\Users\(UserName)\OneDrive\デスクトップ

根本の解決にはなりませんが、使えなくなったショートカットはリンク先が間違っていると思われます。
ショートカットを右クリしプロパティを選択し、ショートカットタブのリンク先を編集してはどうでしょうか。

デスクトップのショートカットからアプリケーションが起動できなくなるケースがあり、原因がわからなく困っています。

具体的には PC の再起動を伴うような Windows Update での更新後に必ず発生します。
インストール先のフォルダ内にあるファイルなどは消えておらず、exe ファイルから直接起動はできますが、デスクトップにあるショートカットからは起動できなくなってしまいます。

アプリケーションを一度アンインストールして、再度インストールすることで問題は解消しますが、条件が条件なので、何が原因なのか調査の方法もわかりません。

対処の糸口だけでも構いません、なにかヒントをお持ちの方がいらっしゃいましたら教えて下さい。