Just a couple of questions that might help people at Piriform to fix the issue...
Were your desktop shortcuts deleted once the cleaning process finished?
Were you only cleaning "Desktop Shortcuts" or you have more items selected?
Are you able to reproduce the problem? If not, you might try to create a broken link on your desktop and run CCleaner again and see if the shortcut gets deleted...