Android - Where are displayed shortcuts stored?

App specific settings are usually stored in the internal storage folder accessible only to that app. While apps do have the ability to write to external storage and lose access to that data when you mount it, I doubt that is the case here.

When you install and move an app to the SD Card, you are not moving the entire app. Some core content of the app still stays on the internal storage. However, moving an app to the external storage has some interesting side effects. The app is completely disabled when you connect your device to the computer, on pre honeycomb devices. Android 3.0 onwards, the USB storage was switched to MTP, which allows the device and the computer to access the storage simultaneously.

In your case, when you connect to the computer, the apps on the SD Card are disabled, causing them to disappear temporarily. As for them not reappearing when you disconnect and restart your phone suggests that there is a bug in the launcher you're using. Try using a different third party launcher instead.

There is no common desktop in Android. The desktop or the better term, the Home screen and its content changes based on the Launcher currently set as default. Desktop is also no directory in Android unlike traditional Linux distributions where you can simply browse them using command-line or a file manager.

Anyhow, most of the Launchers including the stock Android, Nova Launcher, Apex, Smart Launcher Pro, Slim Launcher prefer stores the Home screen shortcuts and widgets into a database located inside their data directory.

E.g. /data/data/com.android.launcher3/databases/launcher.db may have a table named favorites where you may find all those entries. Delete those entries, restart and changes would be reflected on Home screen.

If you want to backup those Home screen shortcuts then backup the whole Launcher app or at least its databases.