If you want to search for emails that have been protected using AD Rights Managed Service using EWS there are a few challenges. How RMS works with Email it is documented in the following Exchange Protocol document https://msdn.microsoft.com/en-us/library/cc463909(v=exchg.80).aspx. The important part when it comes to searching is PidNameContentClass property https://msdn.microsoft.com/en-us/library/office/cc839681.aspx which on RMS messages gets set to rpmsg.message. So to search for this Internet Header you can use a SearchFilter like the following to define the ExtendProperty to search folder
Putting it together in a script that searches a Folder in a Mailbox based on a MailboxName and FolderPath This script is on GitHub https://github.com/gscales/Powershell-Scripts/blob/master/GetRMSItems.ps1 (An important point to note while you can find email that has been protected using RMS with EWS you won't be able to read the encrypted contents using EWS).
One last sample that does a statistics report of all RMS items in a Mailbox using a SearchFilter on the AllItems Search Folder (which is created by the Outlook Desktop client) this outputs a report of the RMS Items and the size of those item in each folder that looks like
This script is on GitHub at https://github.com/gscales/Powershell-Scripts/blob/master/GetRMSItems.ps1