Recycle Bin isn't working: all the files are deleted immediately and completely
In the terminal, enter the following:

ls ~/.Trash

If you get a response "No such file or directory", then just simply restart your Mac. If not, then type this to the terminal if you're an admin:

sudo rm -ri ~/.Trash

Follow the prompts, then restart your Mac.

Source: http://www.thexlab.com/faqs/trash.html#Anchor-Empty-49575