We redirect the desktops like you tried, however we lock them down to prevent deletion of the icons. If you are using profiles you can allocate a default desktop and they can have exclusive rights to their own desktop, allowing them to add and remove data. However, to keep things simple (from a backup pespective) we redirect all their documents to a certain location, so by locking down the desktop it forces them to save data in the "my documents", so when we backup we don't need to worry about different locations of data.
In my opinion, locking down the desktop and redirecting it is more ideal, as you can then manage which icons appear for certain users.
You can script it of course, depends on how many icons you want to add. I'm sure there is a point where the script will be so long, that a redirection might be the faster option.
Script method I've seen used
'Set a path to the executable on the computer for your chosen software in a constant
Const strSoftwareA = "C:\Program Files\Software\certainfile.filetype"
'Check if that software Exists on the computer using your Constant
IF objFSO.FolderExists(strsoftwareA) = true Then
'If a certain file exists, that means it is installed and therefore we make the link
'The lnk file is a shortcut to the executable.
MakeIcon "\SoftwareA.lnk", (strSoftwareA & "certainexe.exe"), "", "", (strSoftwareA & "certainexe.exe, 1"), "Software A Name", strSoftwareA