What I have learned today about the Recycle Bin Security behaviour:
- The items in the recycle bin are only visible for the user who has deleted them. It's not accessible to all users who had access to that document.
- The "Recycle Bin" is only visible in the quick launch bar if you have the permission level "Delete Items". But ... if you click "View all site content" you can see the link to the recycle bin (bug?)
- Only a site collection administrator can see the recycle bin of the end users and the site collection recycle bin. Users with "Full Control" do not have acces.