Error message when moving a document to recycle bin

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 :

Error
You are not allowed to view this document or perform this action.

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.