Might seem like an odd question to exclude documents that have been deleted from a search, but when Destroying documents you have an option to retain the metadata which causes them to show up in a search. I looked through the Records Management search options and I can't find an option to exclude Destroyed records.