I am able to see the deleted records in the Recycle Bin. But when we try to query the deleted records using the QueryAll/IsDeleted/AllRows keywords the query is not returning the records.
However, the query
SELECT Id,IsDeleted,IsPrivate,OwnerId,ParentId FROM Note WHERE Id = '00X0903940' is working fine for system admin profile .
However , It fails and give no records for the different profile. The record is still there inside the recycle bin