Microsoft Exchange deleted items

Two users claim to have lost unread messages on the same day from e-mail inbox. Explained the normal procedure of recovery from recycle bin. Users claim cannot find in recycle bin. Is this possible, if so will I have to administer a backup for these two users lost data?