It seems like you're doing stuff the wrong way round.

Instead of having shortcuts to files that might not exist yet, why not create the shortcuts when you create the files as part of the build/batch process?

The reason the file doesn't go to the recycle bin is because it's easier to delete a file with DeleteFile than it is to use COM to move it to the recycle bin. This is an example of "that feature isn't there because someone would have to program it", and anyone who thought that deleting the shortcut might need to be an undoable action would probably not delete the shortcut without a prompt.