I assume you are logged in as an administrator. Can you make a new admin account and see if you can delete via that account?
After using System Restore to resolve some problems with user profiles, I found that all my Internet Shortcuts on My Desktop had become corrupt. If I try to delete them I receive an error message "Access Denied - Make sure the disc is not full or write protected and that the file is not currently in use"
I can add new shortcuts to the desktop and they work fine.
Any advice would be much appreciated.