Steps to reproduce :
1 . Login with a regular user
2 . Create a document (it doesn't matter if it's WebHome or not)
3 . Delete the document - you will be asked if you want to move the document to recycle bin or not
4 . You will see an error saying :
The document is successfully moved to recycle bin (you can see it listed it Main/AllDocs?view=deletedDocs livetable if you login with an admin user).
The strange part is that there are times when there is no error message, but I couldn't figure out why there is this behavior. The logs don't show anything about these docs.