With App-V, you can either choose to deploy the application to the machine or to the user. If you choose for users, all extension points (including shortcuts) get published as soon, in your case, a sync against the publishing server takes place. These syncs
can be controlled by GPO's, and happen on logon and/or periodic times.
I suppose you all have this in place, otherwise you would not see shortcuts at all. Are you using machine or user deployment?
Do these shortcuts disappear for all users? Are you using roaming profiles (or any other USV methode?)
Roy Essers