I am sorry that your client has this problem, but I am glad to see your post. I was beginning to think that I was the only person seeing this.
I have several desktops that have this issue. They might have one or two shortcuts disappear every few days or they may go for weeks without losing one. One system lost more than half in one day. Some shortcuts were to files/apps on a server, but others where local. e.g. a shortcut to the network and sharing center. Some shortcuts that went away are used every weekday - so it should not be a desktop cleanup routine.
My laptop has done this too; in particular, the shortcuts to each network adapter that I added to my desktop.
I don't have solution for you, but I do have a few questions:
What theme are they using?
Because of some apps that I run I must use the basic theme and I tell the OS to adjust that for best performance.
Do you use MS RDC/RDP to access these computers?
If so, are you using RDP 8
Any other remote control software installed?
I've not put too much effort in solving this since Windows 7 is already costing us many lost man hours... but I am curious as to the cause/solution.
These systems are near my desk, so see them every work day. I don't use all of them myself, I just see them. The users ask me why this happens and I help them put them back. It probably does not matter, but I make the icons via:
right click on a file
select copy from the context menu
right click on the desktop
select paste shortcut from the context menu
I thought about writing a little app that inventories the shortcuts and writes the status/time to a log file so that I could try to correlate the disappearing act with events in the OS events logs... but I have more pressing matters to solve with Windows 7.