Also depending on your version of EV you may have an issue with deletions occuring if you do not have storage expiry set up . Without it orphaned shortcuts will not delete.
You may also need to run a fat orphaned shortcut check to delete all of them...
HKLM\SOFTWARE\KVS\Enterprise Vault\Agents\OrphanedShortcutCheckType
1 –> Fat mode
and then there is a defect with some versions of EV running Fat orphaned shortcut deletions detailed here:
http://www.symantec.com/business/support/index?page=content&id=TECH163851
Lastly, if the shortcuts are from another archive, they may just not delete at all.
I would suggest using Exchange Mailbox Manager to delete the IPM.Note.EnterpriseVault.Shortcut message class. I would ensure that you no longer have any pending items because it is possible that deleteing those items may result in the loss of them.
If this helps or someone helped you resolve this, please note the thread accordingly.
Many thanks and hope this helps,