Did you accidentally delete the Recycle Bin icon itself from the Desktop in Windows Vista? Here is how to restore it back:
Click Start, type right-click on the Desktop, click Personalize, and in the left pane, click Change desktop icons.
In the Desktop Icon Settings dialog, enable the checkbox for Recycle Bin
When you right-click on the Recycle Bin icon in Windows Vista, there is a Delete option, which need not exist for the Recycle Bin. It’s due to this that accidental deletion of the Recycle Bin icon occurs. To remove the Delete option from the Recycle bin context menu, see post Hide the “Delete” command from Recycle Bin Context menu in Vista.
After restoring the Recycle Bin, you may also experience another problem with the Recycle Bin icon not refreshing correctly. Resolution for this problem is posted in this article Recycle Bin icon does not refresh automatically.