A user wanted to find all messages to and from a certain address, so he created a search folder using the predefined 'Mail to and from specific person'. He uses the Del key to quickly file his email and discovered the search folder wasn't finding mail in the Deleted Items folder, even though he added the Deleted Items folder to the list of folders to search.
This is due to an explicit exclusion for the Deleted Items and Junk Email folders in the MAPI search terms used for the predefined folders. As a result, these folders are not included in any of the predefined Search folders.
When you need to include the Deleted Items in the search results, you'll need to create the search folder yourself. Because the Filter doesn't support OR searches, you won't be able to create a To/From search in the default interface, but it can be created using the QueryBuilder or code.
The QueryBuilder is not exposed in the Search folder filter, so you'll need to create the QueryBuilder key in the registry to enable it. Instructions and a ready to use reg file are at Using Query Builder
After adding the QueryBuilder key, you'll be able to create OR searches. For a To/From search, you'll add four criteria and use the OR operator.
- To field contains [email address]
- To contains [sender's display name]
- From field contains [email address]
- From contains [sender's display name]
If you need to include additional addresses (as my user did), repeat the lines as needed.
Select the mailbox and subfolders to search and you're set to go.
I also have a macro that can create the Search folder from the Sender's address on a message in your mailbox. However, you won't be able to add additional addresses to it - it's limited to the address and display name on the message. The macro and instructions are at Use VBA to create an Outlook Search Folder for Sender
Finally, I do not recommend using the Deleted Items folder for storage. You should use a Quick Step or Outlook 2016's Archive command to file the messages in a different folder, where they can't as easily be accidently deleted or subject to mailbox cleanup initiated by the administrator.