That happens when you mistakenly choose Delete instead of Empty the Trash when you are emptying the Recycle Bin. The Vista Beta testers bitched about that option being called "Delete" because the user is in fact trying to delete something when he empties the RB.
Easily fixed.
Right click on your desktop and choose Personalize. In the left Pane, called the Task Pane, click on Change Desktop Icons. Put the checkmark back in the box by the Recycle Bin in the Desktop Icons Settings window which appears.
Colin Barnhorst