I really don't like the suggestion of reformatting as the answer to all problems - sure it will fix the problem, but it's like having a faulty spark plug (or whatever) and saying, "replace the whole motor".

There are other options - like I installed Desksweeper that removes all icons - including recycle bin from the desk with one click - but there should be a fix like a registry entry that will put back the option in the right click menu - like the reg entry that adds send-to and move-to.