Hi,
I think you should definetly create a tracker issue (if none already exists) about this problem, with most details as possible, and a complete way (step by step, with settings) to see the problem.
And then, indicate the link to the issue, so that everybody can vote/comment on it.
In my opinion, backup settings shouldn't have influence on the recycle bin, and recycle bin should always allow to recover everything that was existing, despite the backup settings.
Séverin